2025/10/23 by Rajendraprasad, Deepak, Sankaranarayanan, Durga R.
#05C50 #05C69 #15A18 #15A42 #Combinatorics (math.CO) #FOS: Mathematics #Spectral Theory (math.SP)
paper · doi:10.48550/arxiv.2510.20318
For a finite simple undirected graph G, let γ(G) denote the size of a smallest dominating set of G and μ(G) denote the number of eigenvalues of the Laplacian matrix of G in the interval [0,1), counting multiplicities. Hedetniemi, Jacobs and Trevisan [Eur. J. Comb. 2016] showed that for any graph G, μ(G) \leqslant γ(G). Cardoso, Jacobs and Trevisan [Graphs Combin. 2017] asks whether the ratio γ(T)/μ(T) is bounded by a constant for all trees T. We answer this question by showing that this ratio is less than 4/3 for every tree. We establish the optimality of this bound by constructing an infinite family of trees where this ratio approaches 4/3. We also improve this upper bound for trees in which all the vertices other than leaves and their parents have degree at least k, for every k \geqslant 3. We show that, for such trees T, γ(T)/μ(T) < 1 + 1/((k-2)(k+1)).