Relief of Trees and Its Application

Centrality measures are used to quantify the influence or importance of vertices within a graph. The stress of an internal vertex u in a connected graph G is a centrality measure defined as the number of shortest paths passing through a vertex u in a graph G. In this paper, we introduce a new vertex-based invariant, complementing to stress, called relief of a vertex u in a connected graph G denoted by $$Re_{G}(u)$$ and is defined as the number of shortest paths not passing through a vertex u in a graph G. The sum of relief of all vertices of a connected graph G is called relief of G denoted by Re(G). We obtain the relief of a vertex in a tree and hence obtain the relief of trees. We construct a tree where relief and stress of a vertex is the same. Further linear regression analysis of the relief with the physico-chemical properties of alkanes is carried out. The linear model, based on the relief shows good correlation with the physico-chemical properties of alkanes.