Find in Library

A graph is a <i>block graph</i> if its blocks are all cliques. In this paper, we study the average eccentricity of block graphs from the perspective of <i>block order sequences</i>. 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mfrac><mn>1</mn><mi>n</mi></mfrac><mrow><mo>⌊</mo><mfrac><mn>3</mn><mn>4</mn></mfrac><msup><mi>n</mi><mn>2</mn></msup><mo>−</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><mi>n</mi><mo>⌋</mo></mrow></mrow></semantics></math></inline-formula>, respectively, where <i>n</i> is the order of the block graph. Finally, we devise a linear time algorithm to calculate the block order sequence.