On a poset of trees (Q532127): Difference between revisions

The main object of the paper is the following operation on trees. Let \(G_2\) be a tree and \(x\) and \(y\) be its vertices such that all interior points of the path \(xy\) (if they exist) have degree \(2\) in \(G_2\). The generalized tree shift (GTS) of \(G_2\) is the tree \(G_1\) obtained from \(G_2\) as follows: let \(z\) be the neighbour of \(y\) lying on the path \(xy\), we erase all the edges joining \(y\) and \(N(y)\backslash \{z\}\) and add the edges joining \(x\) and \(N(y)\backslash\{z\}\). A GTS is called proper if neither \(x\) nor \(y\) is a leaf. We say that \(G_1\) follows \(G_2\) if \(G_1\) can be obtained from \(G_2\) by some proper GTS. The author observes that this relation induces a partial order on the set of all trees with \(n\) vertices, that the star is the unique maximal element and the path is the unique minimal element of this partial order. After that, the author shows that some graph-theoretical parameters, such as the number of closed walks of length \(\ell\), the spectral radius and the Estrada index, are monotone functions with respect to this partial order. The author mentiones that \textit{H. Deng} [MATCH Commun. Math. Comput. Chem. 62, No.~3, 599--606 (2009; Zbl 1224.05295)] proved similar results on the Estrada index.