Classification of graphs by Laplacian eigenvalue distribution and independence number

2021/11/24 by Jinwon Choi, Choi, Jinwon, Sunyo Moon +3 · 1 citation
Mathematics · Computer Science · Chemistry · #Graph theory and applications #Computational Drug Discovery Methods #Synthesis and Properties of Aromatic Compounds

paper · pdf · doi:10.48550/arxiv.2111.12380

Abstract

Let m_GI denote the number of Laplacian eigenvalues of a graph G in an interval I and let α(G) denote the independence number of G. In this paper, we determine the classes of graphs that satisfy the condition m_G[0,n-α(G)]=α(G) when α(G)= 2 and α(G)= n-2, where n is the order of G. When α(G)=2, G ≅ K₁ ∇ K_n-m ∇ K_m-1 for some m ≥ 2. When α(G)=n-2, there are two types of graphs B(p,q,r) and B'(p,q,r) of order n=p+q+r+2, which we call the binary star graphs. Also, we show that the binary star graphs with p=r are determined by their Laplacian spectra.

Cited by

• Girth and Laplacian eigenvalue distribution

Related

• Laplacian Distribution and Domination
• On graphs with some normalized Laplacian eigenvalue of extremal multiplicity
• Characterization of graphs with some normalized Laplacian eigenvalue of multiplicity n-3
• Full characterization of graphs having certain normalized Laplacian eigenvalue of multiplicity n-3
• On Distribution of Laplacian Eigenvalues of Graphs