On the ordering of trees by the Laplacian coefficients
From MaRDI portal
Publication:734934
DOI10.1016/J.LAA.2009.07.022zbMath1194.05088arXiv1104.4280OpenAlexW1986246991MaRDI QIDQ734934
Publication date: 14 October 2009
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
Abstract: We generalize the results from [X.-D. Zhang, X.-P. Lv, Y.-H. Chen, extit{Ordering trees by the Laplacian coefficients}, Linear Algebra Appl. (2009), doi:10.1016/j.laa.2009.04.018] on the partial ordering of trees with given diameter. For two $n$-vertex trees $T_1$ and $T_2$, if $c_k (T_1) leqslant c_k (T_2)$ holds for all Laplacian coefficients $c_k$, $k = 0, 1, ..., n$, we say that $T_1$ is dominated by $T_2$ and write $T_1 preceq_c T_2$. We proved that among $n$ vertex trees with fixed diameter $d$, the caterpillar $C_{n, d}$ has minimal Laplacian coefficients $c_k$, $k = 0, 1,..., n$. The number of incomparable pairs of trees on $leqslant 18$ vertices is presented, as well as infinite families of examples for two other partial orderings of trees, recently proposed by Mohar. For every integer $n$, we construct a chain ${T_i}_{i = 0}^m$ of $n$-vertex trees of length $frac{n^2}{4}$, such that $T_0 cong S_n$, $T_m cong P_n$ and $T_i preceq_c T_{i + 1}$ for all $i = 0, 1,..., m - 1$. In addition, the characterization of the partial ordering of starlike trees is established by the majorization inequalities of the pendent path lengths. We determine the relations among the extremal trees with fixed maximum degree, and with perfect matching and further support the Laplacian coefficients as a measure of branching.
Full work available at URL: https://arxiv.org/abs/1104.4280
Cites Work
- On the largest eigenvalues of trees with perfect matchings
- Laplacian coefficients of trees with given number of leaves or vertices of degree two
- On the minimal energy of trees with a given diameter
- Minimum energy on trees with \(k\) pendent vertices
- Starlike trees are determined by their Laplacian spectrum
- On the Laplacian coefficients of acyclic graphs
- Graphs cospectral with starlike trees
- On the Laplacian coefficients of unicyclic graphs
- Ordering trees by the Laplacian coefficients
- On the Laplacian spectral radius of a tree.
- On the index of caterpillars
- A connection between ordinary and Laplacian spectra of bipartite graphs
- No star-like trees are Laplacian co-spectral
- A survey of graph laplacians
- Wiener index of trees: Theory and applications
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
Related Items (22)
Laplacian coefficient, matching polynomial and incidence energy of trees with described maximum degree ⋮ Signless Laplacian coefficients and incidence energy of unicyclic graphs with the matching number ⋮ The signless Laplacian coefficients and the incidence energy of unicyclic graphs with given pendent vertices ⋮ The signless Laplacian coefficients and the incidence energy of graphs with a given bipartition ⋮ Comparison between Kirchhoff index and the Laplacian-energy-like invariant ⋮ Laplacian coefficients of trees with a given bipartition ⋮ On the Laplacian coefficients of graphs under some transformations ⋮ The signless Laplacian coefficients and incidence energy of bicyclic graphs ⋮ On the Laplacian coefficients and Laplacian-like energy of unicyclic graphs with \(n\) vertices and \(m\) pendant vertices ⋮ The signless Laplacian coefficients and the incidence energy of the graphs without even cycles ⋮ On the Laplacian coefficients of trees with a perfect matching ⋮ Each \((n,m)\)-graph having the \(i\)-th minimal Laplacian coefficient is a threshold graph ⋮ Ordering trees and graphs with few cycles by algebraic connectivity ⋮ On the Laplacian coefficients of unicyclic graphs with prescribed matching number ⋮ The Laplacian spectral radius of trees and maximum vertex degree ⋮ On the Laplacian coefficients of tricyclic graphs ⋮ Ordering trees by their Laplacian spectral radii ⋮ Ordering of trees with fixed matching number by the Laplacian coefficients ⋮ On the Laplacian coefficients of bicyclic graphs ⋮ On the Laplacian coefficients and Laplacian-like energy of bicyclic graphs ⋮ Minimizing the Laplacian-energy-like of graphs ⋮ When (signless) Laplacian coefficients meet matchings of subdivision
Uses Software
This page was built for publication: On the ordering of trees by the Laplacian coefficients
