论文标题
拉普拉斯的特征值分布，直径和统治树木
Laplacian eigenvalue distribution, diameter and domination number of trees
论文作者
论文摘要
对于图形$ g $，具有统治数量$γ$，Hedetniemi，Hedetniemi，Jacobs和Trevisan [欧洲组合学杂志53（2016）66-71]证明，$ m_ {g} [0,1）\ leqleqγ$，其中$ m_ {g} $ $ gen $ gen $ genval in l laplacian gen laplacian gen laplacian gen laplacian gen laplace in laplacian of laplacian of laplacian of laplacian $ [0,1）$。令$ t $是直径$ d $的树。在本文中，我们表明$ m_ {t} [0,1）\ geq（d+1）/3 $。但是，对于一般图，这样的下限是错误的。所有实现下限的树木都完全表征。此外，对于树$ t $，我们通过表明$ t $的支配数等于$（d+1）/3 $，并且仅当它具有$（d+1）/3 $ laplacian eigenvalues时，我们就建立了laplacian特征值，直径和支配数量之间的关系。作为一种应用，它还提供了一种新型的树木，它显示了由于Hedetniemi，Jacobs和Trevisan引起的不平等的清晰度。
For a graph $G$ with domination number $γ$, Hedetniemi, Jacobs and Trevisan [European Journal of Combinatorics 53 (2016) 66-71] proved that $m_{G}[0,1)\leq γ$, 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.
