Trees with minimal Laplacian coefficients
Trees with minimal Laplacian coefficients
复制标题
DOI：
10.1016/j.camwa.2010.01.047
复制
发表时间：
2010-04
期刊：
影响因子：
--
通讯作者：
Aleksandar Ilić
中科院分区：
文献类型：
--
作者：
Aleksandar Ilić
设G是一个简单无向图，其Laplacian矩阵L（G）的特征多项式为P（G，μ）=∑k= 0 n（−1）kckμn−k.众所周知，对于树，拉普拉斯系数cn− 2等于图G的维纳指数，而cn− 3等于图G的修正超维纳指数。本文刻画了具有给定匹配数m且同时极小化所有Laplacian系数的n-顶点树。极树A（n，m）是从具有n-m +1个顶点的星星图Sn−m+1通过将悬挂边附加到Sn−m+1的某些m−1个非中心顶点中的每一个而得到的一个支线。特别地，A（n，m）最小化了树的Wiener指数、修正的超Wiener指数和最近引入的关联能量，定义为IE（G）=∑k= 0 n μk，其中μ k是无符号Laplacian矩阵Q（G）=D（G）+A（G）的特征值.我们引入了一个一般的ρ变换，同时减少所有的拉普拉斯系数。最后，我们举例说明了维纳指数和关联能量，同时最大化所有拉普拉斯系数的相反的问题没有解决方案。
Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix L(G), P(G,μ)=∑k=0n(−1)kckμn−k. It is well known that for trees the Laplacian coefficient cn−2is equal to the Wiener index of G, while cn−3is equal to the modified hyper-Wiener index of the graph. In this paper, we characterize n-vertex trees with given matching number m which simultaneously minimize all Laplacian coefficients. The extremal tree A(n,m) is a spur, obtained from the star graph Sn−m+1with n−m+1 vertices by attaching a pendant edge to each of certain m−1 non-central vertices of Sn−m+1. In particular, A(n,m) minimizes the Wiener index, the modified hyper-Wiener index and the recently introduced Incidence energy of trees, defined as IE(G)=∑k=0nμk, where μkare the eigenvalues of signless Laplacian matrix Q(G)=D(G)+A(G). We introduced a general ρ transformation which decreases all Laplacian coefficients simultaneously. In conclusion, we illustrate on examples of Wiener index and Incidence energy that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution.