The Average Eccentricity of Block Graphs: A Block Order Sequence Perspective

Abstract

A graph is a block graph if its blocks are all cliques. In this paper, we study the average eccentricity of block graphs from the perspective of block order sequences. An equivalence relation is established under the block order sequence and used to prove the lower and upper bounds of the eccentricity on block graphs. The result is that the lower and upper bounds of the average eccentricity on block graphs are 1 and 1n⌊34n2−12n⌋, respectively, where n is the order of the block graph. Finally, we devise a linear time algorithm to calculate the block order sequence.

Keywords

• block order sequence
• block graphs
• average eccentricity