Minimising the eccentricity index in trees with given segment sequence

Abstract

The eccentricity index of a graph is the sum of the eccentricities of all vertices in the graph. A segment S of a tree T is a subgraph isomorphic to a non-trivial path where all internal vertices have degree 2 in T and the end-vertices are branching vertices or leaves. The segment sequence of a tree is the sequence of the lengths of all segments in a tree. In this paper, we characterise trees of a given segment sequence with minimum eccentricity index. We show that in the family of trees of a given segment sequence, the tree with minimum eccentricity index is the unique ‘starlike’ tree (a tree with one branching vertex).