An Edge Operation That Increases the Hitting Time Index of Trees

Abstract

Suppose that G is an n-vertex tree with a path Pk attached to a vertex b∈G and with another pendant vertex c that is also attached to b. If G* is the tree constructed from G by moving the attachment point of the path from b to c, then under the hypothesis n≥2k+2 we have HT(G*)>HT(G). This result allows us to exhibit families of trees with a monotonic behavior of the values of their HT index: the index increases as the number of pendant vertices decreases, thus giving support to the conjecture that the maximum HT index among n-vertex trees is attained by the n-path.