Graphs with the minimum spectral radius for given independence number

2022/06/18 by Hu, Yarong, Huang, Qiongxiang, Lou, Zhenzhen · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2206.09152

Abstract

Let \mathbbG_n,α be the set of connected graphs with order n and independence number α. Given k=n-α, the graph with minimum spectral radius among \mathbbG_n,α is called the minimizer graph. Stevanović in the classical book [D. Stevanović, Spectral Radius of Graphs, Academic Press, Amsterdam, 2015.] pointed that determining minimizer graph in \mathbbG_n,α appears to be a tough problem on page 96. Very recently, Lou and Guo in \citeLou proved that the minimizer graph of \mathbbG_n,α must be a tree if α≥\lceil(n)/(2)\rceil. In this paper, we further give the structural features for the minimizer graph in detail, and then provide of a constructing theorem for it. Thus, theoretically we completely determine the minimizer graphs in \mathbbG_n,α along with their spectral radius for any given k=n-α≤ (n)/(2). As an application, we determine all the minimizer graphs in \mathbbG_n,α for α=n-1,n-2,n-3,n-4,n-5,n-6 along with their spectral radii, the first four results are known in \citeXu,Lou and the last two are new.

Cited by

• Characterizing A_σ-minimizer graphs: given order and independence number

Related

• The minimum spectral radius of graphs with a given domination number
• Disproof of a conjecture on the minimum spectral radius and the domination number
• Graphs of order n and diameter 2(n-1)/3 minimizing the spectral radius
• The minimal spectral radius with given independence number
• Characterizing A_σ-minimizer graphs: given order and independence number