2023/05/07 by Santanu Mandal, Mandal, Santanu, Ranjit Mehatari +2 · 1 citation
Chemistry · Computer Science · Mathematics · #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Synthesis and Properties of Aromatic Compounds #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2305.04252
openalex publication_date 2023/05/07 · openalex created_date 2023/05/10 · openalex updated_date 2026/07/28
In this paper we consider particular graphs defined by Kα1∪ Kα2∪⋯ ∪ Kαk, where k is even, Kα is a complete graph on α vertices, ∪ 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 (α1, α2, …, αk). Our primary question is what invariants or graph properties can be deduced form 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.