Laplacian eigenvalue distribution, diameter and domination number of trees

arXiv2212.05283MaRDI QIDQ6420131FDOQ6420131

Authors: Jiaxin Guo, Jie Xue, Rui-fang Liu 

Publication date: 10 December 2022

Abstract: For a graph $G$ with domination number $gamma$, Hedetniemi, Jacobs and Trevisan [European Journal of Combinatorics 53 (2016) 66-71] proved that $m_G[0,1)leqgamma$, where $m_G[0,1)$ means the number of Laplacian eigenvalues of $G$ in the interval $[0,1)$. Let $T$ be a tree with diameter $d$. In this paper, we show that $m_T[0,1)geq(d+1)/3$. However, such a lower bound is false for general graphs. All trees achieving the lower bound are completely characterized. Moreover, for a tree $T$, we establish a relation between the Laplacian eigenvalues, the diameter and the domination number by showing that the domination number of $T$ is equal to $(d+1)/3$ if and only if it has exactly $(d+1)/3$ Laplacian eigenvalues less than one. As an application, it also provides a new type of trees, which show the sharpness of an inequality due to Hedetniemi, Jacobs and Trevisan.

This page was built for publication: Laplacian eigenvalue distribution, diameter and domination number of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6420131)