On the ordering of trees by the Laplacian coefficients

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

14 pages, 6 figures

Scientific paper

We generalize the results from [X.-D. Zhang, X.-P. Lv, Y.-H. Chen, \textit{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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On the ordering of trees by the Laplacian coefficients does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the ordering of trees by the Laplacian coefficients, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the ordering of trees by the Laplacian coefficients will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-178630

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.