首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Laplacian coefficients of trees with given number of leaves or vertices of degree two
Authors:Aleksandar Ili&#x;  Milovan Ili&#x;
Institution:aFaculty of Sciences and Mathematics, ViŠegradska 33, 18 000 Niš, Serbia;bFaculty of Information Technology, Trg Republike 3, 11 000 Beograd, Serbia
Abstract:Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix View the MathML source. It is well known that for trees the Laplacian coefficient cn-2 is equal to the Wiener index of G, while cn-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.
Keywords:Laplacian coefficients  Laplacian matrix  Wiener index  Starlike trees  Pendent vertices
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号