Domination number and Laplacian eigenvalue of trees

被引：0
作者：
Xue J. [1 ]
Liu R. [1 ]
Yu G. [2 ]
Shu J. [3 ]
机构：
[1] School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan
[2] Department of Mathematics, Lingnan Normal University, Zhanjiang, Guangdong
[3] Department of Computer Science and Technology, East China Normal University, Shanghai
来源：
Linear Algebra and Its Applications | 2020年 / 592卷
基金：
中国国家自然科学基金;
关键词：
Diameter; Domination number; Laplacian eigenvalue; Multiplicity;
D O I：
10.1016/j.laa.2020.01.025
中图分类号：
学科分类号：
摘要：
A dominating set in a graph G is a vertex set S⊆V(G) such that any vertex in V(G)S is adjacent to a vertex of S. The domination number γ(G) is the minimum cardinality of a dominating set of G. It is well known that γ(G)≥(d(G)+1)/3, where d(G) is the diameter of G. Let T be a tree on n vertices with diameter d(T). We show that γ(T)=(d(T)+1)/3 if and only if T contains a Laplacian eigenvalue of multiplicity n−d(T), and such trees are completely determined. As an application, we show that some trees are determined by their Laplacian spectra. © 2020 Elsevier Inc.
引用
收藏
页码：210 / 227
页数：17
相关论文
共 24 条
  • [1] Andreotti E., Remondini D., Servizi G., Bazzani A., On the multiplicity of Laplacian eigenvalues and Fiedler partitions, Linear Algebra Appl., 544, pp. 206-222, (2018)
  • [2] Bondy J.A., Murty U.S.R., Graph Theory, Grad. Texts in Math., 244, (2008)
  • [3] Cvetkovic D., Rowlinson P., Simic S., An Introduction to the Theory of Graph Spectra, (2010)
  • [4] Cardoso D.M., Jacobs D.P., Trevisan V., Laplacian distribution and domination, Graphs Combin., 33, pp. 1283-1295, (2017)
  • [5] Desormeaux W.J., Haynes T.W., Henning M.A., Improved bounds on the domination number of a tree, Discrete Appl. Math., 177, pp. 88-94, (2014)
  • [6] Delavina E., Pepper R., Waller B., Lower bounds for the domination number, Discuss. Math. Graph Theory, 30, pp. 475-487, (2010)
  • [7] Faria I., Permanental roots and the star degree of a graph, Linear Algebra Appl., 64, pp. 255-265, (1985)
  • [8] Gunthard H.H., Primas H., Zusammenhang von graphtheorie und mo-theotie von molekeln mit systemen konjugierter bindungen, Helv. Chim. Acta, 39, pp. 1645-1653, (1956)
  • [9] Grone R., Merris R., Sunder V.S., The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl., 11, pp. 218-238, (1990)
  • [10] Grone R., Merris R., The Laplacian spectrum of a graph II, SIAM J. Discrete Math., 7, pp. 221-229, (1994)
123