Eccentricity sequence of a graph of finite diameter

From Graph
Revision as of 17:41, 28 May 2012 by Vipul (talk | contribs)

Definition

For a finite graph

Suppose is a finite connected undirected graph. The eccentricity sequence of is defined as follows: for each vertex of , calculate the eccentricity of that vertex. We obtain a list (possibly with repetitions) of length equal to the size of the vertex set of . The eccentricity sequence is obtained by sorting this list in descending order (i.e., we get a non-increasing, though not necessarily a strictly decreasing, sequence).

Note that not every non-increasing sequence arises as the eccentricity sequence of a graph.