Laplacian eigenvalue distribution, diameter and domination number of trees

被引:1
作者
Guo, Jiaxin [1 ]
Xue, Jie [1 ]
Liu, Ruifang [1 ]
机构
[1] Zhengzhou Univ, Sch Math & Stat, Zhengzhou, Peoples R China
基金
中国国家自然科学基金;
关键词
Laplacian eigenvalue; eigenvalue distribution; trees; CONNECTIVITY; SPECTRUM; GRAPH;
D O I
10.1080/03081087.2024.2385991
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a graph G with domination number gamma, Hedetniemi, Jacobs and Trevisan (2016) proved that $ m_{G}[0,1)\leq \gamma $ mG[0,1)<=gamma, where $ m_{G}[0,1) $ mG[0,1) means the number of Laplacian eigenvalues of G in the interval $ [0,1) $ [0,1). Let T be a tree with diameter d. In this paper, we show that $ m_{T}[0,1)\geq (d+1)/3 $ mT[0,1)>=(d+1)/3. All trees achieving the lower bound are completely characterized. Moreover, we prove that the domination number of a tree is $ (d+1)/3 $ (d+1)/3 if and only if it has exactly $ (d+1)/3 $ (d+1)/3 Laplacian eigenvalues less than one. As an application, it also provides a new type of tree, which shows the sharpness of the inequality due to Hedetniemi, Jacobs and Trevisan.
引用
收藏
页码:763 / 775
页数:13
相关论文
共 23 条
[1]   Laplacian eigenvalue distribution and graph parameters [J].
Ahanjideh, M. ;
Akbari, S. ;
Fakharan, M. H. ;
Trevisan, V. .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 632 :1-14
[2]   On the distribution of Laplacian eigenvalues of trees [J].
Braga, Rodrigo O. ;
Rodrigues, Virginia M. ;
Trevisan, Vilmar .
DISCRETE MATHEMATICS, 2013, 313 (21) :2382-2389
[3]  
Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6
[4]   Laplacian Distribution and Domination [J].
Cardoso, Domingos M. ;
Jacobs, David P. ;
Trevisan, Vilmar .
GRAPHS AND COMBINATORICS, 2017, 33 (05) :1283-1295
[5]  
Cvetkovi D., 1980, SPECTRA GRAPHS
[6]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[7]   THE LAPLACIAN SPECTRUM OF A GRAPH [J].
GRONE, R ;
MERRIS, R ;
SUNDER, VS .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1990, 11 (02) :218-238
[8]   The kth Laplacian eigenvalue of a tree [J].
Guo, Ji-Ming .
JOURNAL OF GRAPH THEORY, 2007, 54 (01) :51-57
[9]  
Haynes T. W., 1998, Fundamentals of Domination in Graphs
[10]   Domination number and Laplacian eigenvalue distribution [J].
Hedetniemi, Stephen T. ;
Jacobs, David P. ;
Trevisan, Vilmar .
EUROPEAN JOURNAL OF COMBINATORICS, 2016, 53 :66-71