Article ID Journal Published Year Pages File Type
9655165 Discrete Applied Mathematics 2005 19 Pages PDF
Abstract
We study the behavior of the Randić index χ subject to the operation on a tree T which creates a new tree T′≠T by deleting an edge ax of T and adding a new edge incident to either a or x. Let ≼mso be the smallest poset containing all pairs (T,T′) such that χ(T)<χ(T′) and T,T′∈Cn (where Cn is the collection of trees with n vertices and of maximum degree 4). We will determine the maximal and minimal elements of (Cn,≼mso). We present an algorithm to construct χ-monotone chains of trees T0,T1,T2,…,Tm such that Ti≺msoTi+1. As a corollary of our results, we present a new method to calculate the first values of χ on Cn.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,