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 $\frac{1}{n}\lfloor \frac{3}{4}{n}^2-\frac{1}{2}n\rfloor$, respectively, where n is the order of the block graph. Finally, we devise a linear time algorithm to calculate the block order sequence.

1. Introduction

We consider connected simple undirected graphs in this paper. $V\left(G\right)$ and $E\left(G\right)$ are the vertex set and the edge set of a graph G, respectively. The size of a graph is the cardinality of its edge set. In a graph G, the set of neighbors of v is $N_G\left(v\right)$, while the degree of v is $de{g}_G\left(v\right)=\left|N_G\left(v\right)\right|$. The distance $d(u,v)$ between u and v is the length of a shortest path between then. The eccentricity $ϵ\left(v\right)$ of a vertex v is the maximum distance from v to all the other vertices in a graph. The diameter and the radius of a graph G are, respectively, the maximum and the minimum eccentricity over all vertices in G.

Topological indices are tools to character entire graphs, especially in chemical graph theory. The average eccentricity $aecc\left(G\right)$ of a graph G is the mean value of eccentricities over all vertices in G, i.e., $aecc\left(G\right)=\frac{1}{\left|V\right(G\left)\right|}\underset{v\in V\left(G\right)}{\Sigma }ϵ\left(v\right)$. The average eccentricity is another distance metric on a graph and introduced by [1]. Directly relying on a polynomial algorithm for the All-Pairs Shortest Paths Problem [2], the average eccentricity can be calculated in time complexity $O(n^{3}logn)$ where n is the order of the graph. The properties, formulas, and bounds on the average eccentricity have recently been studied intensely [3,4,5,6,7,8,9,10,11,12]. Several other topological indices have also been well studied, such as Steiner (revised) Szeged index [13], Wiener Polarity Index [14], connective eccentricity index [15], and eccentric connectivity index [16]. Recently, Mao et al. [17] surveyed the progress of Steiner-type topological indices. On chemical graphs, Ahmad et al. [18] studied the chemical graphs of copper oxide and carbon graphite. They computed and gave close formulas of eccentricity based topological indices, such as total eccentricity index and average eccentricity index for chemical graphs of carbon graphite and copper oxide.

This paper is organized as follows. Basic terminologies and formulas are stated in Section 2. We establish the equivalence relation and bounds of the average eccentricity on block graphs with order n in Section 3. As supports for Section 3, Section 4 and Section 5 study the bounds over the set of block graphs with the same block order sequence and the set of path-like block graphs, respectively. In addition, we devise a linear time algorithm to extract the block order sequence for a block graph G in Section 6. Finally, we conclude our paper by looking forward to future work in Section 7.

2. Preliminaries

In a path P, a vertex is named as an endpoint of P if its degree is exactly one in P. Otherwise, it is called an internal vertex in P. If u and v are the two endpoints of a path P, we shortly use $u\sim v$ or $v\sim u$ to stand for the path P. A path P is simple if every vertex is distinct from the other vertices of P. A vertex v is said to be a cut-vertex of a graph G if its deletion increases the number of connected components of G. Otherwise, it is said to be a non-cut-vertex. If every block of a graph is a clique, then the graph is named as a block graph.

A block graph is said to be a trivial block graph if and only if it has only one block. In a non-trivial block graph, a block is said to be a pendent block if it interacts with a unique block. Therefore a pendent-block has exactly one cut vertex. The other vertices in a pendent block must be non-cut-vertices. We call the non-cut-vertices of a pendent block pendent vertices of the block graph.

Lemma 1. 

There are at least two pendent blocks in a non-trivial block graph.

Proof. 

Let G be a non-trivial block graph. Let $\mathcal{B}=\{B_i:1\le i\le \alpha \}$ be the set of blocks in G where $\alpha$ is the total number of blocks in G. Let C be the set of cut-vertices in G. We construct a new graph H as follows. The vertex set $V\left(H\right)$ is $A\cup C$ where A is a new vertex set such that $\left|A\right|=\alpha$ and there is a bijective function $f:A\to \mathcal{B}$ from the vertex set A to the block set $\mathcal{B}$. Two vertices $u,v\in V\left(H\right)$ are adjacent if and only if the following two situations occur simultaneously.

• u and v are in A and C, respectively.
• There is a vertex $w\in V\left(f\right(u\left)\right)$ such that w and v are adjacent in the graph G.

Now, we show that H is exactly a tree. H is connected due to the connectedness of G. Suppose on the contrary that there is a cycle Q in H. As every vertex in A is not adjacent with the other vertices of A, and every vertex in C is also not adjacent with the other vertices of C, the vertices on the cycle Q come from A and C alternatively. Hence, at least two vertices, say u and v, of Q are from A. Therefore, the two blocks $f\left(u\right)$ and $f\left(v\right)$ are in the same block of G, which is a contradiction. Therefore, H is a tree.

According to the construction of H, the degree of every vertex from C must be at least two in H. So every leaf of H must be a vertex in A. As G is a non-trivial block graph, A must has at least two vertices, so H must has at least three vertices. Hence, H has at least two leaves [19]. Therefore, G has at least two pendent blocks.   □

Let $S=\{(b_i,s_i):1\le i\le k$ and $i,k\in \mathbb{Z}\}\subseteq {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$ be an ordered pair set on the positive integer set ${\mathbb{Z}}^{+}$. The set S is named as a block order sequence if for each ordered pair $(b_i,s_i)(1\le i\le k)$, $b_i$ is not less than two. Then, for every integer i ( $1\le i\le k$), $b_i$ stands for the order of some block and $s_i$ stands for the number of blocks with order $b_i$. Therefore, k represents the cardinality of block orders. Let $\mathcal{G}\left(S\right)=\mathcal{G}\left(\{(b_i,s_i):1\le i\le k\}\right)$ be the set of all block graphs with the block order sequence S.

By the above definitions, for a block graph $G\in \mathcal{G}\left(\{(b_i,s_i):1\le i\le k\}\right)$, the number of blocks $\alpha$, the order n and the size m of G are presented in the following Theorem 1.

Theorem 1. 

Let $G\in \mathcal{G}(\{(b_i,s_i):1\le i\le k\}\subseteq {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+})$ be a block graph. Then we have:

• The number of blocks in G is

  $$\alpha =\underset{i=1}{\overset{k}{\Sigma }}{s}_i$$

  (1)
• The order of G is

  $$n=\underset{i=1}{\overset{k}{\Sigma }}\left(b_i{s}_i\right)-\alpha +1=\underset{i=1}{\overset{k}{\Sigma }}\left(s_i(b_i-1)\right)+1$$

  (2)
• The size of G is

  $$m=\frac{1}{2}\underset{i=1}{\overset{k}{\Sigma }}\left((b_i^2-b_i)s_i\right)$$

  (3)

Proof. 

By the definition of $(b_i,s_i)$ in a block order sequence, $s_i$ stands for the number of blocks with order $b_i$. To sum all, there are, in total, $\alpha =\underset{i=1}{\overset{k}{\Sigma }}{s}_i$ blocks in block graphs with the given block order sequence. For every block with order $b_i$, the number of edges in such a block is $\frac{b_I(b_i-1)}{2}$. Therefore, on the whole, there are ${\Sigma }_{i=1}^k\frac{b_I(b_i-1)}{2}{s}_i$ edges in all blocks. This value is equal to the size of the block graph. In the following, we calculate the order of G.

By the definition, for every $(b_i,s_i)$, the total number of vertices in all blocks with order $b_i$ is $b_i{s}_i$. In total, then, there are $\underset{i=1}{\overset{k}{\Sigma }}\left(b_i{s}_i\right)$ vertices in all blocks. However, this value is larger than the order of G, as some vertices are shared by more than one block.

Now we prove that there are $\alpha -1$ shared vertices in a block graph with $\alpha$ blocks. If $\alpha =1$, the block graph has just one block. Trivially, there are no shared vertices. Suppose $\alpha =p$; there are $p-1$ shared vertices. We are going to prove that when $\alpha =p+1$, there are p shared vertices.

Let G be a block graph with $p+1$ blocks. By Lemma 1, let Q be a pendent block. Let v be the unique cut vertex in Q. Delete all vertices $V\left(Q\right)\backslash \left\{v\right\}$ from G. Then we obtain a graph $G^{\prime }$ with exactly p blocks. By the induction, there are $p-1$ shared vertices in $G^{\prime }$. Now we add Q to $G^{\prime }$ in order to obtain G. Q and $G^{\prime }$ must share exactly one vertex, so there are p shared vertices in G. Therefore, in total there are $\alpha -1$ shared vertices in a block graph with $\alpha$ blocks.

So the order of a block graph is $\underset{i=1}{\overset{k}{\Sigma }}\left(b_i{s}_i\right)-\alpha +1=\underset{i=1}{\overset{k}{\Sigma }}\left(s_i(b_i-1)\right)+1$.   □

In particular, a block graph is said to be a star-like block graph if and only if there is a unique cut-vertex in it. By the definitions, we have,

Theorem 2. 

Let $G\in \mathcal{G}(\{(b_i,s_i):1\le i\le k\}\subseteq {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+})$ be a star-like block graph. The average eccentricity of G is

$$aecc\left(G\right)\ge \left\{\begin{array}{cc}2-\frac{1}{n},\hfill & \alpha >1\hfill \\ 1,\hfill & \alpha =1\hfill \end{array}\right.,$$

(4)

where α is the number of blocks in G and calculated by Equation (1).

Proof. 

If $\alpha =1$, there is a unique block in G. The unique block is a complete graph. So the eccentricity of every vertex is 1. Hence, the average eccentricity of G is 1.

If $\alpha >1$, by definition, there is only one cut-vertex in a start-like block graph. Therefore, the eccentricity of the unique cut-vertex is 1, while the eccentricity of each of the other vertices is 2. Hence, the average eccentricity of the star-like block graph is $\frac{2(n-1)+1}{n}=2-\frac{1}{n}$.    □

In terms of contributions, this paper achieves the following two main results.

• The lower and upper bounds of the average eccentricity on block graphs. We established an equivalence relation on the set of graphs with order n from the perspective of block order sequence, which is going to be presented in Theorem 3. The equivalence relation naturally partitions the set of block graphs with order n into several equivalent classes. Recall that all graphs in every such equivalent class have the same block order sequence. Thus, to bind the average eccentricity on block graphs with order, n is transformed to bind the value on every equivalent class. This transformation seems independently interesting.
• A linear time algorithm to find out a block order sequence. Algorithm 1 is devised to find out the block order sequence of a block graph. The algorithm is proven to be in linear time by Theorem 16. This result shows that it is practicable and available to study the eccentricity on block graphs from the perspective of its block order sequence.

3. Extremal Values on Block Graphs with Order n

Let $\mathcal{G}\left(n\right)$ be the set of block graphs with order n. We define a binary relation $\mathcal{R}\subseteq \mathcal{G}\left(n\right)\times \mathcal{G}\left(n\right)$ over the set $\mathcal{G}\left(n\right)$ where, for every two graphs, $G,H\in \mathcal{G}\left(n\right)$, $(G,H)\in \mathcal{R}$ if and only if G and H have the same block order sequence. We name the relation $\mathcal{R}$ the sequence-equivalence relation.

Theorem 3. 

The sequence-equivalence relation $\mathcal{R}$ on $\mathcal{G}\left(n\right)$ is an equivalence relation.

Proof. 

It is easy to verify that the relation is reflexive, symmetric, and transitive as follows.

• For every graph $G\in \mathcal{G}\left(n\right)$, $(G,G)\in \mathcal{R}$, so it is reflexive.
• $(G,H)\in \mathcal{R}$ if and only if $(H,G)\in \mathcal{R}$ for every two graphs $G,H\in \mathcal{G}\left(n\right)$, so it is symmetric.
• for $G_1,G_2,G_3\in \mathcal{G}\left(n\right)$, if $(G_1,G_2)\in \mathcal{R}$ and $(G_2,G_3)\in \mathcal{R}$, then $(G_1,G_3)$ must be in the relation $\mathcal{R}$, so it is transitive.

Therefore the sequence-equivalence relation $\mathcal{R}$ is reflexive, symmetric and transitive. So it is an equivalence binary relation.    □

As the sequence-equivalence relation $\mathcal{R}$ is an equivalence relation, it partitions the graph set $\mathcal{G}\left(n\right)$ into several equivalence classes. Let $\mathcal{G}\left(n\right)/\mathcal{R}=\{\mathcal{G}\left(S_i\right):1\le i\le l\left(n\right)\}$ be the set of all equivalence classes where each $\mathcal{G}\left(S_i\right)$ is an equivalence class formed by $\mathcal{R}$ and $l\left(n\right)$ is the cardinality of $\mathcal{G}\left(n\right)/\mathcal{R}$. The set $\mathcal{G}\left(n\right)/\mathcal{R}$ is also named as the quotient of $\mathcal{G}\left(n\right)$ by $\mathcal{R}$ [20].

Recall that all graphs in every equivalent class of $\mathcal{G}\left(n\right)/\mathcal{R}$ have the same block order sequence. Therefore, the minimum lower bound among all equivalent classes is the lower bound of the block graphs with order n, while the maximum upper bound among all equivalent classes is the upper bound of the block graph with order n. Therefore, the lower and upper bounds are written as:

$$\underset{\mathcal{G}\left(S_i\right)\in \mathcal{G}\left(n\right)/\mathcal{R}}{min}\left[\underset{G\in \mathcal{G}\left(S_i\right)}{min}\left(aecc\left(G\right)\right)\right]\le aecc\left(G\right)\le \underset{\mathcal{G}\left(S_i\right)\in \mathcal{G}\left(n\right)/\mathcal{R}}{max}\left[\underset{G\in \mathcal{G}\left(S_i\right)}{max}\left(aecc\left(G\right)\right)\right]$$

Therefore, the problem of bounding the average eccentricity on block graphs with order n is transformed to the problem of bounding the average eccentricity on block graphs with the same block order sequence.

By Theorem 8 in Section 4, for any block order sequence S, the lower bound on block graphs with block order sequence S is either $2-\frac{1}{n}$ for $\alpha >1$, or 1 for $\alpha =1$. Recall that, if $\alpha =1$, then the block graph is a complete graph with order n, so the lower bound on block graphs with order n is 1.

In addition, by Theorem 10 in Section 4, for a given block order sequence S, the upper bound of the average eccentricity on block graphs with block order sequence S is $aecc\left(P{G}_{max}^S\right)$, where $P{G}_{max}^S$ is a path-like block graph with the maximum average eccentricity among the set of path-like block graphs with block order sequence S which is defined in Theorem 13 in Section 5. Therefore, the upper bound on block graphs with order n is $\underset{\mathcal{G}\left(S_i\right)\in \mathcal{G}\left(n\right)/\mathcal{R}}{max}\left\{aecc\left(P{G}_{max}^{S_i}\right)\right\}$. Thus, the average eccentricity of block graphs with order n can be bounded by Theorem 4.

Theorem 4. 

Let G be a block graph of order n. Then we have

$$1\le aecc\left(G\right)\le \underset{\mathcal{G}\left(S_i\right)\in \mathcal{G}\left(n\right)/\mathcal{R}}{max}\left\{aecc\left(P{G}_{max}^{S_i}\right)\right\}.$$

Theorem 14 in Section 5 decides the value of $\underset{\mathcal{G}\left(S_i\right)\in \mathcal{G}\left(n\right)/\mathcal{R}}{max}\left\{aecc\left(P{G}_{max}^{S_i}\right)\right\}$ and shows that the upper bound is $\frac{1}{n}\lfloor \frac{3}{4}{n}^2-\frac{1}{2}n\rfloor$.

Integrating Theorems 4 and 14, we achieve the bounds of average eccentricity on block graphs with order n in the following Theorem 5.

Theorem 5. 

Let G be a block graph of order n. Then we have

$$1\le aecc\left(G\right)\le \frac{1}{n}\lfloor \frac{3}{4}{n}^2-\frac{1}{2}n\rfloor .$$

4. Bounds on Block Graphs with a Fixed Block Order Sequence

Now we study the bounds and corresponding extremal graphs over the set of block graphs having the same block order sequence. Before establishing bounds and extremal graphs, we define a notations $G_{(u,v)}$ as follows. Let $(u,v):u,v\in V\left(G\right)$ be an ordered vertex pair where u is a cut vertex of G and $u\ne v$. Let $G_1$ be a graph obtained by removing the edges, each of which is not only incident with u but also on a simple path from u to v in G. Let $G_{(u,v)}$ be a connected component of $G_1$ such that $G_{(u,v)}$ contains the vertex u (see Figure 1 as an example). In particular, if $u=v$, then let $G_{(v,v)}=G$.

To obtain the lower bound and the corresponding extremal graph, we define a block-slide transformation on a graph $G\in \mathcal{G}\left(S\right)$ in Section 4.1. A graph $G^{\prime }$ which is obtained by a block-slide transformation on G satisfies both $aecc\left(G^{\prime }\right)\le aecc\left(G\right)$ and $G^{\prime }\in \mathcal{G}\left(S\right)$. For the upper bound, we define a block-shift transformation on a graph $G\in \mathcal{G}\left(S\right)$ in Section 4.2. A graph $G^{\prime }$ which is obtained by a block-shift transformation on G satisfies both $aecc\left(G^{\prime }\right)\ge aecc\left(G\right)$ and $G^{\prime }\in \mathcal{G}\left(S\right)$.

4.1. The Lower Bound and Corresponding Extremal Graphs

Block-slide transformation: Let $B_i$ be a block in a block graph G depicted in Figure 2, where u and v are two distinct cut-vertices of $B_i$. Let $A=G_{(u,v)}$ and $B=G_{(v,u)}$ be two subgraphs in G (see Figure 2). Let $G^{\prime }=G-\{(u,w)\in E\left(G\right):w\in N_A\left(u\right)\}+\{(v,w):w\in N_A\left(u\right)\}$. The transformation from G to $G^{\prime }$ is named as a block-slide transformation on G. On the other side, the transformation from $G^{\prime }$ to G is named as an inverse block-slide transformation on $G^{\prime }$, i.e., $G=G^{″}-\{(v,w)\in E\left(G^{\prime }\right):w\in N_A\left(v\right)\}+\{(u,w):w\in N_A\left(v\right)\}$.

Theorem 6. 

Each block-slide transformation eliminates exactly one cut-vertex from a block graph.

Theorem 7. 

Let $G^{\prime }$ be a block graph which is obtained by a block-slide transformation on a block graph G (see Figure 2). Then $aecc\left(G^{\prime }\right)\le aecc\left(G\right)$ holds.

Proof. 

Let $B_i$ be a block with order $b_i$ in G. Put the vertices of $B_i$ on a cycle and label its vertices clockwise as $u=u_1$, $u_2$, $u_3$,…,$u_{b_i-1}$, $u_{b_i}$ (see Figure 3). Without loss of generality, let $u_{d_i}=v$. There are $b_i+1$ parts in the graph G. They are $B_i$, $A_1$, $A_2$,…,$A_{b_i-1}$, and $A_{b_i}$, where $A_1=A$, $A_{b_i}=B$, and each $A_j$ is the subgraph $G(u_j,u_1)$ for $2\le j\le b_i-1$. Let $L=max\{ϵ(u_j,A_j):1\le j\le b_i\}$. There are mainly cases of the relationship over $ϵ(u_1,A_1)$, $ϵ(u_{b_i},A_{b_i})$, and L. For each case, we consider the behavior of the average eccentricity on G in the following.

Case 1: $ϵ(u_1,A_1)\le ϵ(u_{b_i},A_{b_i})\le L$. For every vertex $v\in ({\displaystyle \bigcup _{2\le j\le b_i-1}}V\left(A_j\right))\cup V\left(B_i\right)\setminus \left\{u_{b_i}\right\}$, we have $ϵ(v,G)=ϵ(v,G^{″})$. For every vertex $v\in V\left(A_1\right)\setminus \left\{u_1\right\}$, $ϵ(v,G)\ge ϵ(v,G^{″})$. For every vertex $v\in V\left(A_{b_i}\right)$, $ϵ(v,G)\ge ϵ(v,G^{″})$. Hence, the average eccentricity of the whole graph does not increase after a block-slide transformation.

Case 2: $ϵ(u_{b_i},A_{b_i})<ϵ(u_1,A_1)<L$. It is easy to verify that the eccentricity of every vertex in G does not change under the transformation. So the average eccentricity of the whole graph remains the same after a block-slide transformation.

Case 3: $ϵ(u_{b_i},A_{b_i})<ϵ(u_1,A_1)=L$. It is easy to verify that if there is a subgraph $A_j:2\le j\le b_i-1$ such that $ϵ(u_j,A_j)=L$, then the average eccentricity of the whole graph remains the same after the transformation. Let us consider the case that there is no integer $j:2\le j\le b_i-1$ such that $ϵ(u_j,A_j)=L$.

• $ϵ(v,G)=ϵ(v,G^{\prime })$ holds for every vertex $v\in V\left(G\right)\setminus V\left(A_1\right)\setminus V\left(A_{b_i}\right)$.
• $ϵ(v,G)\ge ϵ(v,G^{\prime })$ holds for every vertex $v\in V\left(A_1\right)\setminus \left\{u_1\right\}$.
• $ϵ(v,G)>ϵ(v,G^{\prime })$ holds for every vertex $v\in V\left(A_{b_i}\right)$.
• $ϵ(u_1,G)-ϵ(u_1,G^{\prime })=1$.

As $\left|V\right(A_{b_i}\left)\right|>1$ holds, we have $aecc\left(G^{\prime }\right)\le aecc\left(G\right)$.

Above all, the block-slide transformation does not increase the value of average eccentricity of a block graph. Hence, the theorem holds.    □

Corollary 1. 

Let G be a block graph which is obtained by an inverse block-slide transformation on a block graph $G^{\prime }$ (see Figure 2). Then $aecc\left(G\right)\ge aecc\left(G^{\prime }\right)$ holds.

Theorem 8. 

Every block graph G with a fixed block order sequence satisfies

$$aecc\left(G\right)\ge \left\{\begin{array}{cc}2-\frac{1}{n},\hfill & \alpha >1\hfill \\ 1,\hfill & \alpha =1\hfill \end{array}\right.,$$

where α is the number of blocks in G and calculated by Equation (1).

Proof. 

Let $\{(b_i,s_i):1\le i\le k$ and $i,k\in \mathbb{Z}\}\subseteq {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$ be the block order sequence of the block graph G. We repeatedly apply the block-slide transformation on G until no more such transformation can be applied. As each block-slide transformation eliminates one cut-vertex, the transformation procedure must stop at a state in which there is a unique cut-vertex in the graph. In other words, we achieve a star-like block graph when no more block-slide transformation could be applied to the graph. By Theorem 7, the whole transformation procedure does not increase the average eccentricity. Hence, an n-order star-like block graph reaches the minimum value of the average eccentricity among all block graphs with order n. Finally, by Equation (4), if there is more than one block in G, then $aecc\left(G\right)\ge 2-\frac{1}{n}$. Otherwise, the lower bound is exactly one.    □

4.2. The Upper Bound and Corresponding Extremal Graphs

In this section, we define a block-shift transformation on a block graph and then we present an upper bound on a graph under the help of such a transformation.

Let t be a cut-vertex of a block graph G and $E\left(t\right)$ be the set of edges which are all incident with t. Let $R\left(t\right)$ be a partition of $E\left(t\right)$ such that two edges $(u,t),(v,t)\in E\left(G\right)$ belong to the same element of $R\left(t\right)$ if and only if u and v are in the same block of G. For every element $a\in R\left(t\right)$, the petal $G(a,t)$ corresponding to a is defined as follows. $G(a,t)$ is a connected component of such a graph which is obtained by deleting the edges in ${\displaystyle \bigcup _{b\in R\left(t\right),b\ne a}}b$ from G, and contains the cut-vertex t.

In this section, we will see a special kind of block graph which is named a path-like block graph. A block graph G is named a path-like block graph if it either is a complete graph or has exactly two pendent blocks while each of the other blocks contains exactly two cut-vertices.

Block-shift transformation: Let $B_i$ be a block in a block graph G where t, v, and w are all cut-vertices in $B_i$ as depicted in Figure 4. Note that the three cut-vertices t, w, and v do not need to be distinct to each other. Let C be a petal at the vertex t such that C is a path-like block graph and does not contain the block $B_i$. Let $u\in V\left(C\right)$ be a pendent vertex of G. Let A and B be two sets of petals corresponding, respectively, to vertices w and v, such that $ϵ(w,A)\le ϵ(v,B)$ holds. Let $G^{\prime }=G-\{(w,s)\in E\left(G\right):s\in N_A\left(w\right)\}+\{(u,s):s\in N_A\left(w\right)\}$. Then the transformation from G to $G^{\prime }$ is said to be a block-shift transformation on graph G, while the transformation from $G^{\prime }$ to G is said to be an inverse block-shift transformation on graph $G^{\prime }$, i.e., $G=G^{\prime }-\{(u,s)\in E\left(G^{\prime }\right):s\in N_A\left(u\right)\}+\{(w,s):s\in N_A\left(u\right)\}$.

Theorem 9. 

Let $G^{\prime }$ be a block graph which is obtained by a block-shift transformation on a block graph G (see Figure 4). Then $aecc\left(G^{\prime }\right)\ge aecc\left(G\right)$ holds.

Proof. 

It is obvious that the eccentricity of every vertex in A and B does not decrease under the block-shift transformation. As $ϵ(w,A)\le ϵ(v,B)$, the eccentricity of every vertex in the set $V\left(C\right)\cup V\left(B_i\right)$ also could not be decreased by the block-shift transformation. Above all, after a block-shift transformation, the average eccentricity of a block graph does not decrease.    □

Corollary 2. 

Let G be a block graph which is obtained by an inverse block-shift transformation on a block graph $G^{\prime }$ (see Figure 4). Then $aecc\left(G\right)\le aecc\left(G^{\prime }\right)$ holds.

Repeatedly apply the block-shift transformation on a block graph G. Finally we will reach a state that the graph G turns into a path-like block graph. By Theorem 9, the transformation does not decrease the average eccentricity, so the upper bound on block graph set $\mathcal{G}\left(S\right)$ must be achieved by a path-like block graph in $\mathcal{G}\left(S\right)$. Let $P{G}_{max}^S$ be a path-like block graph with the maximum average eccentricity among all path-like block graphs in $\mathcal{G}\left(S\right)$. The upper bound on the set $\mathcal{G}\left(S\right)$ can be written in the following Theorem 10.

Theorem 10. 

Let $G\in \mathcal{G}\left(S\right)$ be a block graph with the set S as its block order sequence. Then,

$$aecc\left(G\right)\le aecc\left(P{G}_{max}^S\right)$$

The following Section 5 is to present a method to obtain a $P{G}_{max}^S$.

5. Bounds and Extremal Graphs for Path-like Block Graphs

This section settles bounds and extremal graphs for path-like block graphs. Initially, formulas are established to calculate the average eccentricity on a path-like block graph. Then, we set up bounds and their corresponding extremal graphs for the set of path-like block graphs, where every path-like block graph has the same block order sequence S. Finally, we prove lower and upper bounds on the set of path-like block graphs, where each path-like block graph has order n.

5.1. Formulas for the Average Eccentricity on Path-like Block Graphs with Given Block Order Sequence

Let $\mathcal{PG}\left(S\right)\subseteq \mathcal{G}\left(S\right)$ be the set of path-like block graphs with the block order sequence $S\subseteq {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$. For a path-like block graph $G\in \mathcal{PG}\left(S\right)$, we straighten G on a horizontal line from left to right as in Figure 5. Then, we label the blocks as $B_1$, $B_2$, $B_3$,…,$B_{\alpha }$ and label the cut-vertices as $v_1$, $v_2$, $v_3$,…,$v_{\alpha -1}$ in G from left to right, one by one, where $\alpha$ is the number of blocks in G as calculated by Equation (1) in Theorem 1. In particular, we choose a non-cut-vertex from $B_1$ and a non-cut-vertex from $B_{\alpha }$, and then label them $v_0$ and $v_{\alpha }$, respectively. In the following, every path-like block graph has already been straightened and labeled this way. In order to make it clear, in the following, we use $N_i(1\le i\le \alpha )$ to stand for the order of each block $B_i$, i.e., $N_i=\left|V\left(B_i\right)\right|$. Let $\beta =\underset{i=1}{\overset{\lceil \alpha /2\rceil }{\Sigma }}(N_i+N_{\alpha -i+1})(\alpha -i+1)$.

Theorem 11. 

Let $G\in \mathcal{PG}\left(S\right)$ where $S\subseteq {\mathbb{Z}}^{+}\times {\mathbb{Z}}^{+}$ is a block order sequence. Then, the average eccentricity of G is,

• If the number of blocks α is even, then

  $$aecc\left(G\right)=\frac{1}{n}(\beta -\frac{3}{4}{\alpha }^2)$$

  (5)
• If the number of blocks α is odd, then

  $$aecc\left(G\right)=\frac{1}{n}(\beta -\frac{\alpha +1}{2}{N}_{(\alpha +1)/2}-\frac{3}{4}({\alpha }^2-1))$$

  (6)

  where n and α are the order and the number of blocks in G as calculated in Equations (2) and (1), respectively.

Proof. 

If $\alpha$ is even, then in block $B_i$ and $B_{\alpha -i+1}$ for every $1\le i\le \frac{\alpha }{2}$, there are exactly $N_i+N_{\alpha -i+1}-2$ vertices, each of which contributes the value $\alpha -i+1$ to the average eccentricity. The middle cut vertex $v_{\alpha /2}$ exactly contributes the value $\frac{\alpha }{2}$. To sum all, the average eccentricity of G is

$$\begin{array}{cc}\hfill aecc\left(G\right)& =\frac{1}{n}(\underset{i=1}{\overset{\alpha /2}{\Sigma }}(N_i+N_{\alpha -i+1}-2)(\alpha -i+1)+\frac{\alpha }{2})\hfill \\ \hfill & =\frac{1}{n}(\underset{i=1}{\overset{\alpha /2}{\Sigma }}(N_i+N_{\alpha -i+1})(\alpha -i+1)-2\underset{i=1}{\overset{\alpha /2}{\Sigma }}(\alpha -i+1)+\frac{\alpha }{2})\hfill \\ \hfill & =\frac{1}{n}(\beta -\frac{3}{4}{\alpha }^2)\hfill \end{array}$$

If $\alpha$ is odd, then in block $B_i$ and $B_{\alpha -i+1}$ for every $1\le i\le \lfloor \frac{\alpha }{2}\rfloor =\frac{\alpha -1}{2}$, there are exactly $N_i+N_{\alpha -i+1}-2$ vertices, each of which contributes the value $\alpha -i+1$ to the average eccentricity. In addition, each vertex in the middle block $B_{\lceil (\alpha /2)\rceil }$ contributes the value $\lceil \frac{n}{2}\rceil =\frac{n+1}{2}$. To sum all, the average eccentricity of G is

$$\begin{array}{cc}\hfill aecc\left(G\right)& =\frac{1}{n}(\underset{i=1}{\overset{(\alpha -1)/2}{\Sigma }}(N_i+N_{\alpha -i+1}-2)(\alpha -i+1)+\frac{\alpha +1}{2}{N}_{\lceil \alpha /2\rceil })\hfill \\ \hfill & =\frac{1}{n}(\underset{i=1}{\overset{\lceil \alpha /2\rceil }{\Sigma }}(N_i+N_{\alpha -i+1}-2)(\alpha -i+1)-\frac{\alpha +1}{2}(N_{\lceil \alpha /2\rceil }-2))\hfill \\ \hfill & =\frac{1}{n}(\underset{i=1}{\overset{\lceil \alpha /2\rceil }{\Sigma }}(N_i+N_{\alpha -i+1})(\alpha -i+1)-2\underset{i=1}{\overset{\lceil \alpha /2\rceil }{\Sigma }}(\alpha -i+1)-\frac{\alpha +1}{2}{N}_{\lceil \alpha /2\rceil }+(\alpha +1))\hfill \\ \hfill & =\frac{1}{n}(\beta -\frac{\alpha +1}{2}{N}_{(\alpha +1)/2}-\frac{3}{4}({\alpha }^2-1))\hfill \end{array}$$

   □

5.2. Extremal Graphs for Path-like Block Graphs with Given Block Order Sequence

In order to set up bounds and study extremal graphs for path-like block graphs, we need to establish a graph transformation operation which is named as block-exchange transformation. To make the transformation clear, we define a mapping function $M\left(i\right)$ to map the subscript index i of $B_i(1\le i\le \alpha )$ into a new integer as follows.

• If $\alpha$ is even, then

  $$M\left(i\right)=\left\{\begin{array}{c}i1\le i\le \frac{\alpha }{2}\hfill \\ \frac{\alpha }{2}i=\frac{\alpha }{2}+1\hfill \\ M(i-1)-1\frac{\alpha }{2}+2\le i\le \alpha \hfill \end{array}\right.$$

  (7)
• If $\alpha$ is odd, then

  $$M\left(i\right)=\left\{\begin{array}{c}i1\le i\le \lceil \frac{\alpha }{2}\rceil \hfill \\ M(i-1)-1\lceil \frac{\alpha }{2}\rceil +1\le i\le \alpha \hfill \end{array}\right.$$

  (8)

Lemma 2. 

For every block $B_i$ ($1\le i\le \alpha$) in a path-like block graph G, there are exactly $N_i-1$ vertices, each of which has the eccentricity equal to $\alpha -M\left(i\right)+1$.

Proof. 

We prove this lemma by considering the case that $\alpha$ is even. It is the same way to give proof for the case that $\alpha$ is odd. There are three cases.

Case 1: $1\le i\le \frac{\alpha }{2}$. The eccentricity of every vertex $u\in V\left(B_i\right)\setminus \left\{v_i\right\}$ is $\alpha -i+1=\alpha -M\left(i\right)+1$, while the vertex $v_i$ has its eccentricity equal to the value of $\alpha -i$. Hence, the lemma holds on this case.

Case 2: $i=\frac{\alpha }{2}+1$. The eccentricity of every vertex $u\in V\left(B_i\right)\setminus \left\{v_{i-1}\right\}$ is equal to $\frac{\alpha }{2}+1=\alpha -\frac{\alpha }{2}+1=\alpha -M\left(i\right)+1$, while the vertex $v_{i-1}$ has the eccentricity as $\frac{\alpha }{2}$. Hence, the lemma holds on this case.

Case 3: $\frac{\alpha }{2}+2\le i\le \alpha$. The eccentricity of every vertex $u\in V\left(B_i\right)\setminus \left\{v_{i-1}\right\}$ is $\alpha -M\left(i\right)+1$, while the vertex $v_{i-1}$ has the value of $\alpha -M\left(i\right)$. Hence, the lemma holds on this case.

Above all, there are exactly $N_i-1$ vertices each of which has the eccentricity equal to $\alpha -M\left(i\right)+1$ for every block $B_i$ ($1\le i\le \alpha$) in a path-like block graph G.    □

Block-exchange transformation: Let G be a path-like block graph with labeled blocks and cut-vertices as depicted in Figure 5. If there are two distinct blocks $B_i$, $B_j$ ($1\le i,j\le \alpha$) such that both $N_i<N_j$ and $M\left(i\right)<M\left(j\right)$ hold, then we construct a new graph $G^{\prime }$ by exchanging the two blocks $B_i$ and $B_j$ in G, i.e., $G^{\prime }=G-\{(v_{i-1},u):u\in N_{B_i}\left(v_{i-1}\right)\}-\{(v_i,u):u\in N_{B_i}\left(v_i\right)\}+\{(v_{j-1},u):u\in N_{B_i}\left(v_{i-1}\right)\}+\{(v_j,u):u\in N_{B_i}\left(v_i\right)\}-\{(v_{j-1},u):u\in N_{B_j}\left(v_{j-1}\right)\}-\{(v_j,u):u\in N_{B_j}\left(v_j\right)\}+\{(v_{i-1},u):u\in N_{B_j}\left(v_{j-1}\right)\}+\{(v_i,u):u\in N_{B_j}\left(v_j\right)\}$ (see Figure 6). The transformation from G to $G^{\prime }$ is called a block-exchange transformation on G. On the other side, the transformation from $G^{\prime }$ to G is said to be an inverse block-exchange transformation on $G^{\prime }$. Note that, after the block-exchange transformation, $B_i^{{}^{\prime }}\cong B_j$ and $B_j^{{}^{\prime }}\cong B_i$ holds in graph $G^{\prime }$.

Theorem 12. 

Let $G^{\prime }$ be a path-like block graph which is obtained by a block-exchange transformation on a block graph G (see Figure 6). Then $aecc\left(G^{\prime }\right)>aecc\left(G\right)$ holds.

Proof. 

Let $B_i$ and $B_j$ be two blocks such that both $N_i<N_j$ and $M\left(i\right)<M\left(j\right)$ hold in a path-like block graph G. Let $G^{\prime }$ be the new graph obtained by a block-exchange transformation on these two blocks. By the definition of the eccentricity, the eccentricity of every vertex in $V\left(G\right)\setminus V\left(B_i\right)\setminus V\left(B_j\right)\cup \{v_{i-1},v_i,v_{j-1},v_j\}$ does not change under the block-exchange transformation. As $M\left(i\right)<M\left(j\right)$, by Lemma 2, the eccentricity of each vertex in $V\left(B_i\right)\setminus \{v_{i-1},v_i\}$ decreases $(\alpha -M(i)+1)-(\alpha -M(j)+1)=M\left(j\right)-M\left(i\right)$, while the eccentricity of each vertex in $V\left(B_j\right)\setminus \{v_{j-1},v_j\}$ increase $(\alpha -M(i)+1)-(\alpha -M(j)+1)=M\left(j\right)-M\left(i\right)$ after the block-exchange transformation. On the whole, relying on Equations (5) and (6), the change of the average eccentricity under such a transformation is

$$\begin{array}{cc}\hfill aecc\left(G\right)-aecc\left(G^{\prime }\right)& =\frac{1}{n}(((N_i-1)(\alpha -M\left(i\right)+1)+(N_j-1)(\alpha -M\left(j\right)+1))\hfill \\ \hfill & -((N_j-1)(\alpha -M\left(i\right)+1)+(N_i-1)(\alpha -M\left(j\right)+1)))\hfill \\ \hfill & =\frac{1}{n}(N_i-N_j)(M\left(j\right)-M\left(i\right))\hfill \end{array}$$

As $M\left(i\right)<M\left(j\right)$ and $N_i<N_j$ hold, $(N_i-N_j)(M\left(j\right)-M\left(i\right)<0$ must hold. Therefore, the block-exchange transformation increases the average eccentricity of a path-like block graph.    □

Corollary 3. 

Let G be a path-like block graph which is obtained by an inverse block-exchange transformation on a block graph $G^{\prime }$ (see Figure 6). Then $aecc\left(G\right)>aecc\left(G^{\prime }\right)$ holds.

Let $P{G}_{min}^S$ and $P{G}_{max}^S$ be path-like block graphs having, respectively, minimum and maximum average eccentricity on the set of block graphs with block order sequence S. In other words, let $P{G}_{min}^S\in \mathcal{PG}\left(S\right)\subseteq \mathcal{G}\left(S\right)$ be a path-like block graph with the block order sequence S where every two distinct blocks $B_i$ and $B_j$ of $P{G}_{min}^S$ satisfies that both $N_i<N_j$ and $M\left(i\right)<M\left(j\right)$ hold. Let $P{G}_{max}^S\in \mathcal{PG}\left(S\right)$ be a path-like block graph with the block order sequence S where every two distinct blocks $B_i$ and $B_j$ of $P{G}_{max}^S$ satisfies that both $N_i<N_j$ and $M\left(i\right)>M\left(j\right)$ hold.

Theorem 13. 

The average eccentricity of every graph $G\in \mathcal{PG}\left(S\right)$ with block order sequence S is not less than that of $P{G}_{min}^S$ and not larger than that of $P{G}_{max}^S$, i.e.,

$$aecc\left(P{G}_{min}^S\right)\le aecc\left(G\right)\le aecc\left(P{G}_{max}^S\right)$$

Proof. 

Repeatedly applying the block-exchange transformation on graph G until there is no pair of blocks $B_i$ and $B_j$ such that both $N_i<N_j$ and $M\left(i\right)<M\left(j\right)$ hold, we obtain a graph $P{G}_{max}^S\in \mathcal{PG}\left(S\right)$. By Theorem 12, every block-exchange transformation on graph G increases the average eccentricity. Hence, $aecc\left(G\right)\le aecc\left(P{G}_{max}^S\right)$ holds.

Repeatedly applying the inverse block-exchange transformation on graph G until there is no pair of blocks $B_i$ and $B_j$ such that both $N_i<N_j$ and $M\left(i\right)>M\left(j\right)$ hold, we obtain a graph $P{G}_{min}^S\in \mathcal{PG}\left(S\right)$. By Corollary 3, every block-exchange transformation on graph G increases the average eccentricity. Hence, $aecc\left(P{G}_{min}^S\right)\le aecc\left(G\right)$ holds.    □

5.3. Bounds on Path-like Graphs with Order n

Theorem 14. 

Let G be a path-like block graph with the order n. Then we have

$$1\le aecc\left(G\right)\le \frac{1}{n}\lfloor \frac{3}{4}{n}^2-\frac{1}{2}n\rfloor$$

Proof. 

We straighten the graph G relying on the method stated in Section 5.1. The blocks are labeled $B_1$, $B_2$, $B_3$,…,$B_{\alpha }$ and the cut-vertices are labeled $v_1$, $v_2$, $v_3$,…,$v_{\alpha -1}$ in G from left to right, one by one, where $\alpha$ is the number of blocks in G as calculated by Equation (1) in Theorem 1. We regard each non-cut-vertex of $B_1$ and $B_{\alpha }$ as an empty block graph, where an empty block graph is a graph having exactly one vertex. Then, we pick just one non-cut-vertex of $B_1$ and label it $B_0$, while one non-cut-vertex of $B_n\alpha$ is labeled $B_{\alpha +1}$, see Figure 7.

Considering the additional labels $B_0$ and $B_{\alpha +1}$, we slightly modify the mapping function $M\left(i\right)$ as follows, where $M\left(i\right)$ is the mapping function defined in Equations (7) and (8). A new mapping function $M^{{}^{\prime }}\left(i\right)$, which maps the subscript index i of $B_i:0\le i\le \alpha +1$ into a new integer, is defined in the following Equation (9).   

$$M^{{}^{\prime }}\left(i\right)=\left\{\begin{array}{c}0i=1ori=\alpha +1\hfill \\ M\left(i\right)1\le i\le \alpha \hfill \end{array}\right.$$

(9)

In the following proof, we still use $N_i$ to stand for the order of block $B_I$ for every $0\le i\le \alpha +1$. If there is a non-cut vertex $v\in V\left(B_i\right)$ and a block $B_j$ such that $1\le i\le \alpha$, $0\le j\le \alpha +1$, $N_i\ge 3$, and $M^{{}^{\prime }}\left(i\right)>M^{{}^{\prime }}\left(j\right)$, then let $G^{\prime }=G-\{(v,u):u\in N_{B_i}\left(v\right)\}+\{(v,u):u\in V\left(B_j\right)\}$. Repeatedly apply this vertex-moving operation on the vertices of G until no more such operation can be achieved. Then we obtain a path $P_n$. Recall that every such vertex-moving operation increases the average eccentricity. Therefore, the average eccentricity of G could not exceed that of a path $P_n$. Recall that the average eccentricity of an n-order path $P_n$ is $\frac{1}{n}\lfloor \frac{3}{4}{n}^2-\frac{1}{2}n\rfloor$ [4].

On the other hand, if there is a non-cut-vertex $v\in V\left(B_i\right)$ and a block $B_j$ such that $0\le i\le \alpha +1$, $1\le j\le \alpha$, $N_i<n$, and $M^{{}^{\prime }}\left(i\right)<M^{{}^{\prime }}\left(j\right)$, then let $G^{\prime }=G-\{(v,u):u\in N_{B_i}\left(v\right)\}+\{(v,u):u\in V\left(B_j\right)\}$. Repeatedly apply this vertex-moving operation on the vertices of G until no more such operation can be achieved. We will subsequently obtain either a block graph with only one block or a block graph with exactly two blocks. If the final graph has only one block, then it is a complete graph $K_n$. Recall that every such vertex-moving operation decrease the average eccentricity. If the final graph has exactly two blocks, say $B_1$ and $B_2$, then we delete all edges in $B_2$ and add an edge between each vertex $v\in V\left(B_1\right)$ and $u\in V\left(B_2\right)$. Then we still obtain a complete graph $K_n$, and this process decreases the average eccentricity. It is easy to verify that the average eccentricity of a complete graph $K_n$ is exactly one [4].

Above all, we have $1\le aecc\left(G\right)\le \frac{1}{n}\lfloor \frac{3}{4}{n}^2-\frac{1}{2}n\rfloor$, where G is a path-like block graphs with order n.    □

6. Extracting the Block Order Sequence of a Block Graph

In this section, we devised a linear time algorithm to extract the block order sequence of a block graph. This indicates that it is possible to study the eccentricity on block graphs via its block order sequence.

6.1. To Decide a Cut-Vertex

Our algorithm needs to test whether a vertex is a cut-vertex The idea benefits from a property of cut-vertices in a block graph, which is stated in Lemma 3 and realized by Algorithm 2. We should emphasize that Lemma 3 is fit for the block graphs rather than the general undirected simple graphs.

Lemma 3. 

Let G be a block graph and $v\in V\left(G\right)$. Let u be a neighbor of v in G. Then u is a cut-vertex of G if and only if there is a vertex $w\in N_G\left(u\right)$ such that $(v,w)\notin E\left(G\right)$.

Proof. 

Let $G^{\prime }$ be the graph obtained by deleting vertex u from G. We prove this lemma from the following two sides.

On the one hand, if there is a vertex $w\in N_G\left(u\right)$ such that $(v,w)\notin E\left(G\right)$, then v and w is also not adjacent in $G^{\prime }$. We claim that w and v are disconnected in $G^{\prime }$. Otherwise, both in graph G and $G^{\prime }$, there must be a path P from v to w such that $u\notin V\left(P\right)$. The path $P^{{}^{\prime }}=vuw$ is another path from w to v in G and is vertex-internally-disjointed with the path P. Hence, there is a cycle in G which contains the three vertices u, v, and w, so the three vertices u, v, and w are all in the same block of G. As G is a block graph, every block is a clique, so there is an edge incident with both v and w, which comes to a contradiction. Hence, u must be a cut-vertex of G.

On the other hand, if u is a cut-vertex of G, then $G^{\prime }$ must be a disconnected graph. Recall that the graph G is connected. Moreover, there must be two distinct vertices $a\in V\left(G\right)$ and $b\in V\left(G\right)$ such that every simple path from a to b in G must go through the vertex u [19], as u is a cut-vertex. Let $P_1$ be an arbitrary simple path from a to b in G. Without loss of generality, let $w_1\in V\left(P_1\right)$ and $w_2\in V\left(P_1\right)$ satisfy $(w_1,u)\in E\left(P_1\right)$ and $(w_2,u)\in E\left(P_1\right)$, and the sub-path $a\sim w_1$ of $P_1$ from a to $w_1$ do not contain the vertex u. Then the path $P_1$ can be marked as $a\sim w_{1}u{w}_2\sim b$. Assume that every vertex $t\in N_G\left(u\right)\setminus \left\{v\right\}$ is adjacent to v in the graph G. Then the path $P_1^{\prime }=a\sim w_{1}v{w}_2\sim b$ is another path from a to b. Then $P_1^{{}^{\prime }}$ is another simple path, while not containing u at all. This comes to a contradiction.

Above all, the vertex u is a cut-vertex of G if and only if there is a neighbor $w\in N_G\left(u\right)$ of u such that $(v,w)\notin E\left(G\right)$.    □

By Lemma 3, it is exciting to find that, in order to decide whether u is a cut-vertex of a block graph G, one just needs to access all edges which are incident with u rather than decide the connectivity of G. It would therefore take far less time to decide whether a vertex is a cut-vertex in a block graph by use of the property stated in Lemma 3. We realize this decision method in the following Algorithm 2.

Theorem 15. 

Given a vertex v of a graph G and a neighbor $u\in N_G\left(v\right)$ of v, it spends $O\left(\right|N_G\left(u\right)\left|\right)$ time to decide whether u is a cut-vertex by Algorithm 2.

Proof. 

In step 2–2 of Algorithm 2, each neighbor of u is either adjacent to v or not adjacent to v. Moreover, every neighbor of u is visited once and only once. Hence, the time complexity is $O\left(\right|N_G\left(u\right)\left|\right)$.    □

6.2. To Obtain a Block Order Sequence

To find the block order sequence of a block graph G we must first to find every block and then calculate the order for each block, which is realized in Algorithm 1.

Lemma 4. 

Let u be a non-cut-vertex in a block $B_i$ of a block graph G, then the order of $B_i$ is equal to $|N_G\left(u\right)|+1$.

Proof. 

As u is not a cut-vertex, u and all its neighbors $N_G\left(u\right)$ must be in the same block $B_i$. As every block in a block graph must be a clique, there is no vertex $w\in V\left(B_i\right)$ such that $(u,w)\notin E\left(G\right)$. Therefore, the vertex set $V\left(B_i\right)$ is equal to $\left\{u\right\}\cup N_G\left(u\right)$. Hence, the order of $B_i$ is $|N_G\left(u\right)|+1$.    □

Now let us turn to Algorithm 1. The algorithm is to find the block order sequence of a block graph by means of searching the cut-vertices one by one, as every block must associate with some cut-vertex. The whole Algorithm is a recursive depth-first search (DFS) procedure [2] beginning with an arbitrary vertex of a block graph. The process to search for the cut-vertices is an “up-to-bottom” recursive method. The process to calculate the order for each block is performed the back-trace way during the recursive process from bottom to up.

By Lemma 1, the algorithm can always meet with a pendent block, say $B_i$, at the bottom of a recursive process. Let w be the unique cut-vertex in $B_i$. By Lemma 4, the algorithm calculate the order of $B_i$ by means of $\left\{w\right\}\cup N_G\left(w\right)$ where $w\in V\left(B_i\right)$ is not a cut-vertex and adjacent to w. After all the pendents block corresponding to w has been processed, the algorithm marks w as an non-cut-vertex by step 1. Then, the algorithm traces back to search another block. By this way going up, finally, we can obtain a block order sequence of a block graph.

Algorithm 1: Seq(G, v, visit, B)

Algorithm 2: Is_CutVertex(G, v, u)

Theorem 16. 

It takes $O(n+m)$ time for the Algorithm 1 to find the block order sequence of a block graph G where n and m are the order and the size of G, respectively.

Proof. 

Without loss of generality, let Algorithm 1 execute beginning with the vertex v. Let $T(w,G_{(w,v)})$ be the time taken by Algorithm 1 on the subgraph $G_{(w,v)}$. Let C be the set of cut-vertices in G. Then we have,

$$\begin{array}{cc}\hfill T(v,G_{(v,v)})& =\underset{u\in N_G^1\left(v\right)}{\Sigma }\left(O\right(|N_G\left(u\right)\left|\right)+T(u,G_{(u,v)}))+\underset{u\in N_G\left(v\right)}{\Sigma }\left(O\right(|N_G\left(u\right)\left|\right)+O(1))\hfill \\ \hfill & =\underset{u\in C}{\Sigma }\left(O\right(|N_G\left(u\right)\left|\right))+\underset{u\in V\left(G\right)}{\Sigma }\left(O\right(|N_G\left(u\right)\left|\right))+O\left(n\right)\hfill \\ \hfill & \le 2\underset{u\in V\left(G\right)}{\Sigma }\left(O\right(|N_G\left(u\right)\left|\right)+O\left(n\right)=O(n+m)\hfill \end{array}$$

□

7. Conclusions

We study the average eccentricity of block graphs from the perspective of their block order sequences. A block order sequence could provide useful structural information on block graphs and can be obtained in linear time from Algorithm 1. Moreover, via Theorem 3, the perspective of block order sequences naturally provides an equivalence relationship on the set of block graphs. It may be interesting to study some other computational problems and mathematical properties on block graphs from the perspective of block order sequences. Recall that the blocks in the other graph classes may not be all cliques. Moreover, an entire graph can be characterized by applying several criteria [21,22]. In particular, in chemical graph theory, several connections between graph structure and properties have been established [23]. This paper characterizes a block graph from block order sequence. Are there any ways to deal with problems on the other graph classes, also from the perspective of block order sequence?