错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Laplacian eigenvalues and eigenspaces of cographs generated by finite sequence

  • Santanu Mandal,
  • Ranjit Mehatari,
  • Zoran Stanić

摘要

In this paper we consider particular graphs defined by \(\overline{\overline{\overline{K_{\alpha _1}}\cup K_{\alpha _2}}\cup \cdots \cup K_{\alpha _k}}\) K α 1 ¯ K α 2 ¯ K α k ¯ , where k is even, \(K_\alpha \) K α is a complete graph on \(\alpha \) α vertices, \(\cup \) stands for the disjoint union and an overline denotes the complementary graph. These graphs do not contain the 4-vertex path as an induced subgraph, i.e., they belong to the class of cographs. In addition, they are iteratively constructed from the generating sequence \((\alpha _1, \alpha _2, \ldots , \alpha _k)\) ( α 1 , α 2 , , α k ) . Our primary question is which invariants or graph properties can be deduced from a given sequence. In this context, we compute the Lapacian eigenvalues and the corresponding eigenspaces, and derive a lower and an upper bound for the number of distinct Laplacian eigenvalues. We also determine the graphs under consideration with a fixed number of vertices that either minimize or maximize the algebraic connectivity (that is the second smallest Laplacian eigenvalue). The clique number is computed in terms of a generating sequence and a relationship between it and the algebraic connectivity is established.