Disproof of a conjecture on the minimum spectral radius and the domination number

2023/07/28 by Hu, Yarong, Lou, Zhenzhen, Huang, Qiongxiang
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2307.15605

Abstract

Let G_n,γ be the set of all connected graphs on n vertices with domination number γ. A graph is called a minimizer graph if it attains the minimum spectral radius among G_n,γ. Very recently, Liu, Li and Xie [Linear Algebra and its Applications 673 (2023) 233--258] proved that the minimizer graph over all graphs in \mathbbG_n,γ must be a tree. Moreover, they determined the minimizer graph among G_{n,\lfloor(n)/(2)\rfloor} for even n, and posed the conjecture on the minimizer graph among G_{n,\lfloor(n)/(2)\rfloor} for odd n. In this paper, we disprove the conjecture and completely determine the unique minimizer graph among G_{n,\lfloor(n)/(2)\rfloor} for odd n.

Related

• The minimum spectral radius of graphs with a given domination number
• Graphs with the minimum spectral radius for given independence 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