Eccentric Adjacency Index of Graphs with a Given Number of Cut Edges

Abstract

The eccentric adjacency index of an n-vertex-connected and simple graph G is defined as $\xi ^{ad}(G)=\sum \nolimits _{x\in V_G}\dfrac{S_G(x)}{ec_G(x)}$, where $S_G(x)$ is the sum of degrees of neighbors of x and $ec_G(x)$ is the eccentricity of x in G. Denote by ${\mathcal {G}}(n,k)$ the set of n-vertex-connected graphs with k cut edges, where $0\le k\le n-1 (k\ne n-2)$. In this paper, we determine the graph with largest eccentric adjacency index and characterize the extremal graph among all graphs in ${\mathcal {G}}(n,k)$.

1 Introduction

Let G be an n-vertex-connected and simple graph with vertex set $V_G$ and edge set $E_G$. The degree of a vertex x in G, denoted by $\deg _G(x)$, is $\deg _G(x)=|{\varGamma }_G(x)|$, where ${\varGamma }_G(x)$ is the set of neighbors of x in G. A vertex x is called a pendent vertex if $\deg _G(x)=1$. The length of a shortest path connecting the vertices x and y in G is called the distance between x and y and is denoted by $d_G(x,y)$. For a vertex $x\in V_G$, the eccentricity of x in G is $ec_G(x)=\max \nolimits _{y\in V_G}d_G(x,y)$. The radius $r_G$ and the diameter $d_G$ of G are defined by $r_G=\min \nolimits _{x\in V_G}ec_{G}(x)$ and $d_G=\max \nolimits _{x\in V_G}ec_G(x)$, respectively. For a vertex $x\in V_G$, the sum of degrees of neighbors of the vertex x in G is $S_G(x)=\sum \nolimits _{y\in {\varGamma }_G(x)}\deg _G(y)$.

A path from $x_1$ to $x_n$ consisting of vertices $x_1,x_2,\ldots ,x_n$ is written by $x_1x_2\ldots x_n$ and is called $x_1,x_n$-path. The vertices $x_1$ and $x_n$ are the end vertices, and $x_2,x_3,\ldots ,x_{n-1}$ are the internal vertices of the path $x_1x_2\ldots x_n$. A path with length $d_G$ in G is said to be a diametrical path in G. An n-vertex tree with $n-1$ pendant vertices and a vertex of degree $n-1$ is said to be a star and is denoted by $S_n$. An n-vertex simple graph is called a complete graph if every pair of its vertices is linked by an edge and is denoted by $K_n$. A complete subgraph of an n-vertex graph G is called a clique in G.

For $S\subseteq V_G$ and $F \subseteq E_G$, the graphs $G-S$ and $G-F$ are the subgraphs induced by $V_G-S$ and $E_G-F$, respectively. A vertex u (respectively, an edge e) is called a cut vertex (respectively, cut edge) of an n-vertex-connected graph G, if $G-v$ (respectively, $G-e$) has at least two components. A cut edge is called an internal cut edge if it is not a pendent edge. An n-vertex graph G is called a 2-connected (respectively, 2-edge-connected), if $G-v$ (respectively, $G-e)$ is connected, for every $v\in V_G$ (respectively, $e\in E_G)$. An n-vertex-connected graph is said to be a block if it does not have any cut vertex. The cyclomatic number of an n-vertex-connected graph G is $c(G)=m-n+1$, where m is the size of G. In particular, if $c(G)=0$ then G is a tree. If $c(G)=1$ then G is a unicyclic graph, and if $c(G)=2$ then G is a bicyclic graph. Every tree has at most $n-1$ cut edges and an n-vertex-connected graph having cyclomatic number at least one has at most $n-3$ cut edges. Thus, it is obvious from the above statement that for any n-vertex-connected graph with k cut edges, we always have $0\le k\le n-1$ and $k\ne n-2$.

A molecular graph G is a representation of the structural formula of a chemical compound in terms of graph theory. A topological index is a number which characterizes properties of G. Recently, the development of computational chemistry owes much to the topological index of a molecular graph. The topological indices have mainly described the non-empirical molecular structure quantitatively and analyzed the structure and performance of molecules. There are many classes of topological indices; some of them are distance-based, degree-based, degree-distance-based and eccentricity-based indices of graphs. The one of the most used topological indexes, Wiener index, is defined as the sum of all distances between unordered pairs of vertices

$$\begin{aligned} W(G)=\sum \limits _{\{x,y\}\subseteq V_G} d_G(x,y). \end{aligned}$$

Recently, many eccentricity-based topological indices have been defined, e.g., eccentric connectivity index, total eccentricity index, Zagreb eccentricity indices, etc. One of most investigated eccentricity-based indexes is the eccentric connectivity index, which was proposed by Sharma et al. [15]. The eccentric connectivity index is defined as:

$$\begin{aligned} \xi ^c(G)=\sum \limits _{x\in V_G} \deg _G(x)ec_G(x). \end{aligned}$$

(1)

The eccentric connectivity index has been shown to give high level of predictability of pharmaceutical properties and provides leads for the development of safe and useful anti-HIV compounds [7].

The eccentric adjacency index (also known as Ediz eccentric connectivity index [8]) is the modification of eccentric connectivity index and is defined as follows:

$$\begin{aligned} \xi ^{ad}(G)=\sum \limits _{x\in V_G} \frac{S_G(x)}{ec_G(x)}. \end{aligned}$$

(2)

Relationship of eccentric connectivity index and eccentric adjacency index has been investigated by Gupta et al. [10]. The eccentric distance sum was introduced by Gupta et al. [11], which was defined as:

$$\begin{aligned} \xi ^{d}(G)=\sum \limits _{x\in V_G} ec_G(x)D_G(x), \end{aligned}$$

where $D_G(x)=\sum \nolimits _{y\in V_G} d_G(y,x)$ is the sum of all distances from the vertex x.

In recent years, finding the extremal bounds for some topological indices in terms of graph structure parameters, has turned out to be a useful direction in extremal graph theory and many results are obtained. In [1], the authors found the extremal conjugated trees with respect to eccentric connectivity index and eccentric adjacency index. In [2], the authors determined the largest unicyclic graphs with a given girth and largest tree with a fixed diameter with respect to eccentric adjacency index. Akhter [3] derived the extremal trees for eccentric connectivity and eccentric adjacency indices in terms of other graph invariants including matching number, bipartition size, independence number and domination number. Hua [12] determined the smallest value of Wiener index among all n-vertex-connected graphs with k cut edges. Hua et al. [13] characterized the graphs with the smaller eccentric distance sum among all n-vertex-connected graphs with k cut edges. For further studies on topological indices of graphs with given parameters, we refer [4,5,6, 9, 14, 16,17,18,19,20] to the readers.

Motivated by the work referred above, we continue the research on the eccentric adjacency index of graphs with some given parameters. In this paper, we find the graphs with the largest eccentric adjacency index among the n-vertex graphs with a given number of cut edges and characterize the extremal graphs.

2 The Connected Graphs with a Given Number of Cut Edges

Let ${\mathcal {G}}(n,k)$ be the set of n-vertex-connected graphs with k cut edges, where $0\le k\le n-1 (k\ne n-2)$. Denote by $K_{n-k}^k$ the graph obtained by attaching k pendent vertices to a unique vertex of a complete graph $K_{n-k}$. In this section, we find an n-vertex-connected graph in ${\mathcal {G}}(n,k)$ with largest eccentric adjacency index. First, we prove some lemmas which will be crucial to the proof of our main result (Fig. 1).

Lemma 1

Let $H_1$ and $H_2$ be two vertex-disjoint-connected graphs each of order at least 2 with $u\in V_{H_1}$ and $v\in V_{H_2}$. Let $G_1$ be the graph obtained by connecting u and v by an edge uv, and $G_2$ be the graph obtained by identifying u with v and introducing a pendent edge uw with pendent vertex w, respectively. Then $\xi ^{ad}(G_1)<\xi ^{ad}(G_2)$.

Fig. 1

The graphs $G_1$ and $G_2$ in Lemma 1

Proof

For each vertex $x\in V_{G_1}$, we have

$$\begin{aligned} \begin{array}{ll} ec_{G_1}(x)=\max \{ec_{H_1}(x),\ d_{H_1}(x,u)+1+ec_{H_2}(v)\}, &{} \text{ if } x\in V_{H_1},\\ ec_{G_1}(x)=\max \{ec_{H_2}(x),\ d_{H_2}(x,v)+1+ec_{H_1}(u)\}, &{} \text{ if } x\in V_{H_2}. \end{array} \end{aligned}$$

(3)

For each vertex $x\in V_{G_2}{\setminus }\{u,w\}$, we have

$$\begin{aligned} \begin{array}{ll} ec_{G_2}(x)=\max \{ec_{H_1}(x),\ d_{H_1}(x,u)+ec_{H_2}(v),\ d_{H_1}(x,u)+1\}, &{} \text{ if } x\in V_{H_1},\\ ec_{G_2}(x)=\max \{ec_{H_2}(x),\ d_{H_2}(x,v)+ec_{H_1}(u),\ d_{H_2}(x,v)+1\}, &{} \text{ if } x\in V_{H_2}. \end{array} \end{aligned}$$

(4)

Now, it is easily seen that the eccentricities of u and w in $G_2$ are as follows:

$$\begin{aligned} \begin{aligned} ec_{G_2}(u)&=\max \{ec_{H_1}(u),\ ec_{H_2}(v)\},\\ ec_{G_2}(w)&=\max \{ec_{H_2}(u)+1,\ ec_{H_2}(v)+1\}. \end{aligned} \end{aligned}$$

(5)

Note that from (3) and (4), we get $ec_{G_1}(x)\ge ec_{G_2}(x)$ for each $x\in V_{G_1}{\setminus }\{u,v\}$. By the construction of $G_1$ and $G_2$, for each $x\in V_{G_1}{\setminus }(\{u,v,w\}\cup {\varGamma }_{H_1}(u)\cup {\varGamma }_{H_2}(v))$, we have $S_{G_2}(x)=S_{G_1}(x)$. For each $x\in {\varGamma }_{H_1}(u)$, we have

$$\begin{aligned} \begin{aligned} S_{G_1}(x)&=\sum \limits _{y\in {\varGamma }_{H_1}(x){\setminus }\{u\}}\deg _{H_1}(y)+\deg _{H_1}(u)+1,\\ S_{G_2}(x)&=\sum \limits _{y\in {\varGamma }_{H_1}(x){\setminus }\{u\}}\deg _{H_1}(y)+\deg _{H_1}(u)+\deg _{H_2}(v)+1. \end{aligned} \end{aligned}$$

(6)

For each $x\in {\varGamma }_{H_2}(v)$, we have

$$\begin{aligned} \begin{aligned} S_{G_1}(x)&=\sum \limits _{y\in {\varGamma }_{H_2}(x){\setminus }\{v\}}\deg _{H_2}(y)+\deg _{H_2}(v)+1,\\ S_{G_2}(x)&=\sum \limits _{y\in {\varGamma }_{H_2}(x){\setminus }\{v\}}\deg _{H_2}(y)+\deg _{H_1}(u)+\deg _{H_2}(v)+1. \end{aligned} \end{aligned}$$

(7)

Furthermore, the sum of degrees of neighbors of the vertices u, v and w in $G_1$ and $G_2$ is given by

$$\begin{aligned} \begin{aligned} S_{G_1}(u)&=\sum \limits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\deg _{H_2}(v)+1,\\ S_{G_1}(v)&=\sum \limits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+\deg _{H_1}(u)+1,\\ S_{G_2}(u)&=\sum \limits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\sum \limits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+1,\\ S_{G_2}(w)&=\deg _{H_1}(u)+\deg _{H_2}(v)+1. \end{aligned} \end{aligned}$$

(8)

Therefore, from (3) to (8), we obtain

Case I If $ec_{H_1}(u)\ge ec_{H_2}(v)+1$, then

$$\begin{aligned} \begin{aligned} \xi ^{ad}(G_1)-\xi ^{ad}(G_2)&=-\left( \sum \nolimits _{x\in {\varGamma }_{H_1}(u)}\dfrac{\deg _{H_2}(v)}{ec_{G_2}(x)}+\sum \nolimits _{x\in {\varGamma }_{H_2}(v)}\dfrac{\deg _{H_2}(u)}{ec_{G_2}(x)}\right) \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\deg _{H_2}(v)+1}{ec_{H_1}(u)} \\&\quad -\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+1}{ec_{H_1}(u)} \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+\deg _{H_1}(u)+1}{ec_{H_1}(u)+1} \\&\quad -\dfrac{\deg _{H_1}(u)+\deg _{H_2}(v)+1}{ec_{H_1}(u)+1} \\&=-\left( \sum \nolimits _{x\in {\varGamma }_{H_1}(u)}\dfrac{\deg _{H_2}(v)}{ec_{G_2}(x)}+\sum \nolimits _{x\in {\varGamma }_{H_2}(v)}\dfrac{\deg _{H_2}(u)}{ec_{G_2}(x)}\right) \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)-\deg _{H_2}(v)}{ec_{H_1}(u)+1} \\&\quad -\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)-\deg _{H_2}(v)}{ec_{H_1}(u)} <0. \end{aligned} \end{aligned}$$

Case II If $ec_{H_2}(v)\ge ec_{H_1}(u)+1$, then

$$\begin{aligned} \xi ^{ad}(G_1)-\xi ^{ad}(G_2)= & {} -\left( \sum \nolimits _{x\in {\varGamma }_{H_1}(u)}\dfrac{\deg _{H_2}(v)}{ec_{G_2}(x)}+\sum \nolimits _{x\in {\varGamma }_{H_2}(v)}\dfrac{\deg _{H_2}(u)}{ec_{G_2}(x)}\right) \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\deg _{H_2}(v)+1}{ec_{H_2}(v)+1} \\&\quad -\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+1}{ec_{H_2}(v)} \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+\deg _{H_1}(u)+1}{ec_{H_2}(v)} \\&\quad -\dfrac{\deg _{H_1}(u)+\deg _{H_2}(v)+1}{ec_{H_2}(v)+1} \\= & {} -\left( \sum \nolimits _{x\in {\varGamma }_{H_1}(u)}\dfrac{\deg _{H_2}(v)}{ec_{G_2}(x)}+\sum \nolimits _{x\in {\varGamma }_{H_2}(v)}\dfrac{\deg _{H_2}(u)}{ec_{G_2}(x)}\right) \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)-\deg _{H_1}(u)}{ec_{H_2}(v)+1} \\&\quad -\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)-\deg _{H_1}(u)}{ec_{H_2}(v)} <0. \end{aligned}$$

Case III If $ec_{H_1}(u)=ec_{H_2}(v)$, then

$$\begin{aligned} \begin{aligned} \xi ^{ad}(G_1)-\xi ^{ad}(G_2)&=-\left( \sum \nolimits _{x\in {\varGamma }_{H_1}(u)}\dfrac{\deg _{H_2}(v)}{ec_{G_2}(x)}+\sum \nolimits _{x\in {\varGamma }_{H_2}(v)}\dfrac{\deg _{H_2}(u)}{ec_{G_2}(x)}\right) \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\deg _{H_2}(v)+1}{ec_{H_2}(v)+1} \\&\quad -\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+1}{ec_{H_2}(v)} \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+\deg _{H_1}(u)+1}{ec_{H_2}(v)+1} \\&\quad -\dfrac{\deg _{H_1}(u)+\deg _{H_2}(v)+1}{ec_{H_2}(v)+1} \\&=-\left( \sum \nolimits _{x\in {\varGamma }_{H_1}(u)}\dfrac{\deg _{H_2}(v)}{ec_{G_2}(x)}+\sum \nolimits _{x\in {\varGamma }_{H_2}(v)}\dfrac{\deg _{H_2}(u)}{ec_{G_2}(x)}\right) \\&\quad +\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+1}{ec_{H_2}(v)+1}\\&\quad -\dfrac{\sum \nolimits _{y\in {\varGamma }_{H_1}(u)}\deg _{H_1}(y)+\sum \nolimits _{y\in {\varGamma }_{H_2}(v)}\deg _{H_2}(y)+1}{ec_{H_2}(v)}&<0. \end{aligned} \end{aligned}$$

This completes the proof. $\square$

In the following lemma, we prove an elementary result.

Lemma 2

Let $G\ncong K_n$ be an n-vertex-connected graph, and $u,v\in V_{G}$ be non-adjacent vertices of G. Then $\xi ^{ad}(G)<\xi ^{ad}(G+uv)$.

Proof

Observe that $d_G(u,v)\ge 2$ and $d_{G+uv}(u,v)=1$. Let $x\in V_G$ and A be the set of eccentric vertices of x in G, such that $ec_G(x)=d_G(x,u)+d_G(u,v)+d_G(v,y)$, for all $y\in A$. Then

$$\begin{aligned} \begin{aligned} ec_{G+uv}(x)&=d_{G+uv}(x,u)+d_{G+uv}(u,v)+d_{G+uv}(v,y)\\&<d_{G}(x,u)+d_{G}(u,v)+d_{G}(v,y)=ec_G(x). \end{aligned} \end{aligned}$$

(9)

The eccentricities of other vertices of G are same in G and $G+uv$. The sum of degrees of neighbors of the vertices u and v in $G+uv$ is given by

$$\begin{aligned} \begin{aligned} S_{G+uv}(u)&=S_G(u)+\deg _G(v)+1,\\ S_{G+uv}(v)&=S_G(v)+\deg _G(u)+1. \end{aligned} \end{aligned}$$

(10)

For each $x\in {\varGamma }_G(u)$ and $y\in {\varGamma }_G(v)$, we have

$$\begin{aligned} S_{G+uv}(x)=S_G(x)+1,&S_{G+uv}(y)=S_G(y)+1. \end{aligned}$$

(11)

Therefore, from (9) to (11), we obtain

$$\begin{aligned} \begin{aligned} \xi ^{ad}(G)-\xi ^{ad}(G+uv)&\le \dfrac{S_{G}(u)}{ec_{G+uv}(u)}-\dfrac{S_{G}(u)+\deg _{G}(v)+1}{ec_{G+uv}(u)} +\dfrac{S_{G}(v)}{ec_{G+uv}(v)} \\&\quad -\dfrac{S_{G}(v)+\deg _{G}(u)+1}{ec_{G+uv}(v)}+\sum \limits _{x\in {\varGamma }_G(u)}\bigg (\dfrac{S_{G}(x)}{ec_{G+uv}(x)} \\&\quad -\dfrac{S_{G}(x)+1}{ec_{G+uv}(x)}\bigg )+\sum \limits _{y\in {\varGamma }_G(v)}\left( \dfrac{S_{G}(y)}{ec_{G+uv}(y)}-\dfrac{S_{G}(y)+1}{ec_{G+uv}(y)}\right) \\&=-\dfrac{\deg _{G}(v)+1}{ec_{G+uv}(u)}-\dfrac{\deg _{G}(u)+1}{ec_{G+uv}(v)}-\sum \limits _{x\in {\varGamma }_G(u)}\dfrac{1}{ec_{G+uv}(x)}\\&\quad -\sum \limits _{y\in {\varGamma }_G(v)}\dfrac{1}{ec_{G+uv}(y)} \\&<0. \end{aligned} \end{aligned}$$

This completes the proof. $\square$

Lemma 3

Let H be a complete graph of order $n\ge 2$, and $v_1,\ldots ,v_t\in V_H$ be some distinct vertices of H, where $2\le t\le n$. Let $H_1,H_2,\ldots ,H_t$ be the non-trivial connected graphs corresponding to a vertex $v_1,v_2,\ldots ,v_t$, respectively, and $u_1\in V_{H_1}, u_2\in V_{H_2},\ldots ,u_t\in V_{H_t}$. Let $G_3$ be the graph obtained from H by identifying a vertex $u_j\in V_{H_j}$ to a vertex $v_j\in V_H$ for $j=1,\ldots ,t$, respectively. Let $G_4$ be the graph obtained from H by identifying the vertices $u_1,u_2,\ldots ,u_t$ to a vertex, say $v_1\in V_H$, of $v_j'$s. Then $\xi ^{ad}(G_3)<\xi ^{ad}(G_4)$.

Proof

The order of both $G_3$ and $G_4$ is defined as $n=\sum \nolimits _{j=1}^{t}|H_j|-t+|H|$. For each vertex $u\in V_{H_j}$, we have

$$\begin{aligned} \begin{aligned} ec_{G_3}(u)&=\max \{ec_{H_j}(u),\ d_{H_j}(u,u_j)+1+ec_{H_l}(u_l),\ l\ne j\},\\ ec_{G_4}(u)&=\max \{ec_{H_j}(u),\ d_{H_j}(u,u_j)+ec_{H_l}(u_l),\ l\ne j\}. \end{aligned} \end{aligned}$$

(12)

For each $w\in V_H{\setminus }\{v_1,v_2,\ldots ,v_t\}$

$$\begin{aligned} \begin{aligned} ec_{G_3}(w)&=ec_{G_4}(w)=\max \{1+ec_{H_j}(v_j),\ j=1,2,\ldots ,t\}. \end{aligned} \end{aligned}$$

(13)

From (12) and (13), it is obvious that $ec_{G_3}(u)\ge ec_{G_4}(u)$ for each $u\in V_{H_j}$. Let $A=V_{H_j}{\setminus }(V_H\cap V_{H_j})\cup {\varGamma }_{H_j}(u_j)$. Note that $S_{G_3}(x)=S_{G_4}(x)$ for each $x\in A$, where $1\le j\le t$. For each $v_1,v_2,\ldots ,v_t\in V_H\cap V_{H_j}$, $j=1,\ldots ,t$,

$$\begin{aligned} \begin{aligned} \begin{array}{ll} S_{G_3}(v_l)=S_{H}(v_l)+\sum \limits _{\begin{array}{c} j=1,\\ j\ne l \end{array}}^{t}\deg _{H_j}(u_j)+S_{H_l}(u_l),&\text{ for } l=1,2,\ldots ,t. \end{array} \end{aligned} \end{aligned}$$

(14)

Also

$$\begin{aligned} \begin{array}{ll} S_{G_3}(x)=S_{G_4}(x)=S_H(x)+\sum \limits _{j=1}^{t}\deg _{H_j}(u_j), &{} \forall \ x\in V_{H}{\setminus }\{v_1,v_2,\ldots ,v_t\}, \\ S_{G_3}(x)=S_{H_j}(x)+\deg _H(v_j), &{} \forall \ x\in {\varGamma }_{H_j}(u_j), \text{ where } 1\le j\le t. \end{array} \end{aligned}$$

(15)

From (14) and (15), we obtain

$$\begin{aligned} \begin{aligned} \xi ^{ad}(G_3)&=\sum \limits _{l=1}^{t}\dfrac{1}{ec_{G_3}(v_l)} \left( S_{H}(v_l)+\sum \limits _{\begin{array}{c} j=1\\ j\ne l \end{array}}^{t}\deg _{H_j}(u_j)+S_{H_l}(u_l)\right) \\&\quad +\sum \limits _{x\in V_H{\setminus }\{v_1,v_2,\ldots ,v_t\}}\dfrac{1}{ec_{G_3}(x)} \left( S_H(x)+\sum \limits _{j=1}^{t}\deg _{H_j}(u_j)\right) \\&\quad +\sum \limits _{j=1}^{t}\sum \limits _{x\in {\varGamma }_{H_j}(u_j)}\dfrac{1}{ec_{G_3}(x)}(S_{H_j}(x)+\deg _H(v_j)) +\sum \limits _{j=1}^{t}\sum \limits _{x\in A}\dfrac{S_{H_j}(x)}{ec_{G_3}(x)} \\&=\sum \limits _{x\in V_H}\dfrac{S_H(x)}{ec_{G_3}(x)} +\sum \limits _{l=1}^{t}\sum \limits _{\begin{array}{c} j=1\\ j\ne l \end{array}}^{t}\dfrac{\deg _{H_j}(u_j)}{ec_{G_3}(v_l)} +\sum \limits _{l=1}^{t}\dfrac{S_{H_l}(u_l)}{ec_{G_3}(v_l)} \\&\quad +\sum \limits _{j=1}^{t}\sum \limits _{x\in V_H{\setminus }\{v_1,v_2,\ldots ,v_t\}}\dfrac{\deg _{H_j}(u_j)}{ec_{G_3}(x)}+\sum \limits _{j=1}^{t}\sum \limits _{x\in {\varGamma }_{H_j}(u_j)}\dfrac{S_{H_j}(x)}{ec_{G_3}(x)} \\&\quad +\sum \limits _{j=1}^{t}\sum \limits _{x\in {\varGamma }_{H_j}(u_j)}\dfrac{\deg _H(v_j)}{ec_{G_3}(x)}+\sum \limits _{j=1}^{t}\sum \limits _{x\in A}\dfrac{S_{H_j}(x)}{ec_{G_3}(x)}. \end{aligned} \end{aligned}$$

(16)

Furthermore, the sum of the degrees of neighbors of $v_1$ in $G_4$ is as follows:

$$\begin{aligned} \begin{aligned} S_{G_4}(v_1)&=S_H(v_1)+\sum \limits _{j=1}^{t}S_{H_j}(u_j). \end{aligned} \end{aligned}$$

(17)

Also

$$\begin{aligned} \begin{array}{ll} S_{G_4}(x)=S_{H}(x)+\sum \limits _{j=1}^{t}\deg _{H_j}(u_j),&{}\forall \ x\in {\varGamma }_{H}(v_1), \\ \begin{aligned} S_{G_4}(x)&{}=S_{H_l}(x)+\deg _H(v_l)\\ &{}\quad +\sum \limits _{\begin{array}{c} j=1\\ j\ne l \end{array}}^{t}\deg _{H_j}(u_j), \end{aligned}&\forall \ x\in {\varGamma }_{H_l}(u_l), \text{ where } 1\le l\le t. \end{array} \end{aligned}$$

(18)

From (17) and (18), we obtain

$$\begin{aligned} \begin{aligned} \xi ^{ad}(G_4)&=\dfrac{1}{ec_{G_4}(v_1)}\left( S_H(v_1)+\sum \limits _{j=1}^{t}S_{H_j}(u_j)\right) +\sum \limits _{x\in {\varGamma }_{H}(v_1)}\dfrac{1}{ec_{G_4}(x)}\Bigg (S_{H}(x)\\&\quad +\sum \limits _{j=1}^{t}\deg _{H_j}(u_j)\Bigg )+\sum \limits _{l=1}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{1}{ec_{G_4}(x)}\Bigg (S_{H_l}(x) \\&\quad +\deg _H(v_1)+\sum \limits _{\begin{array}{c} j=1\\ j\ne l \end{array}}^{t}\deg _{H_j}(u_j)\Bigg ) +\sum \limits _{j=1}^{t}\sum \limits _{x\in A}\dfrac{S_{H_j}(x)}{ec_{G_4}(x)} \\&=\sum \limits _{x\in {\varGamma }_{H}(v_1)}\dfrac{S_H(x)}{ec_{G_4}(x)} +\sum \limits _{j=1}^{t}\sum \limits _{x\in {\varGamma }_{H}(v_1)}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)} +\sum \limits _{l=1}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{S_{H_l}(x)}{ec_{G_4}(x)} \\&\quad +\sum \limits _{l=1}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{\deg _{H}(v_1)}{ec_{G_4}(x)} +\sum \limits _{l=1}^{t}\sum \limits _{\begin{array}{c} j=1\\ j\ne l \end{array}}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)} \\&\quad +\sum \limits _{j=1}^{t}\sum \limits _{x\in A}\dfrac{S_{H_j}(x)}{ec_{G_4}(x)}. \end{aligned} \end{aligned}$$

Since H is a complete graph, ${\varGamma }_H(v_1)=V_H{\setminus }\{v_1\}$ and the degree of every vertex is same.

$$\begin{aligned} \xi ^{ad}(G_4)= & {} \sum \limits _{j=1}^{t}\dfrac{S_{H_j}(u_j)}{ec_{G_4}(v_1)} +\sum \limits _{x\in V_H{\setminus }\{v_1\}}\dfrac{S_H(x)}{ec_{G_4}(x)} +\sum \limits _{j=1}^{t}\sum \limits _{x\in V_{H}{\setminus }\{v_1\}}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)} \nonumber \\&\quad +\sum \limits _{l=1}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{S_{H_l}(x)}{ec_{G_4}(x)} +\sum \limits _{l=1}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{\deg _{H}(v_1)}{ec_{G_4}(x)} \nonumber \\&\quad +\sum \limits _{l=1}^{t}\sum \limits _{\begin{array}{c} j=1\\ j\ne l \end{array}}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)}+\sum \limits _{j=1}^{t}\sum \limits _{x\in A}\dfrac{S_{H_j}(x)}{ec_{G_4}(x)}\nonumber \\= & {} \sum \limits _{x\in V_H}\dfrac{S_H(x)}{ec_{G_4}(x)}+\sum \limits _{j=1}^{t}\dfrac{S_{H_j}(u_j)}{ec_{G_4}(v_1)}\\&\quad +\sum \limits _{j=1}^{t}\left( \sum \limits _{x\in V_{H}{\setminus }\{v_1,v_2,\ldots ,v_t\}}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)}+\sum \limits _{x\in \{v_2,\ldots ,v_t\}}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)}\right) \nonumber \\&\quad +\sum \limits _{l=1}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{S_{H_l}(x)}{ec_{G_4}(x)}+\sum \limits _{l=1}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{\deg _{H}(v_1)}{ec_{G_4}(x)}\nonumber \\&\quad +\sum \limits _{l=1}^{t}\sum \limits _{\begin{array}{c} j=1\nonumber \\ j\ne l \end{array}}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)} +\sum \limits _{j=1}^{t}\sum \limits _{x\in A}\dfrac{S_{H_j}(x)}{ec_{G_4}(x)}. \end{aligned}$$

(19)

Thus, from (16) and (19), we obtain

$$\begin{aligned} \begin{aligned} \xi ^{ad}(G_3)-\xi ^{ad}(G_4)&\le \sum \limits _{j=2}^{t}\left( \dfrac{S_{H_j}(u_j)}{ec_{G_4}(v_j)} -\dfrac{S_{H_j}(u_j)}{ec_{G_4}(v_1)}\right) \\&\quad +\sum \limits _{j=2}^{t}\sum \limits _{x\in {\varGamma }_{H_j}(u_j)}\left( \dfrac{\deg _{H}(v_j)}{ec_{G_4}(x)} -\dfrac{\deg _H(v_1)}{ec_{G_4}(x)}\right) \\&\quad +\sum \limits _{j=2}^{t}\left( \dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(v_1)}-\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(v_j)}\right) \\&\quad -\sum \limits _{l=1}^{t}\sum \limits _{\begin{array}{c} j=1\\ j\ne l \end{array}}^{t}\sum \limits _{x\in {\varGamma }_{H_l}(u_l)}\dfrac{\deg _{H_j}(u_j)}{ec_{G_4}(x)} \\&<0. \end{aligned} \end{aligned}$$

This completes the proof. $\square$

By elementary calculations, one can easily derive the following lemma.

Lemma 4

Let $K^k_{n-k}$ be an n-vertex-connected graph as described above, where $0\le k\le n-1 (k\ne n-2)$. Then

$$\begin{aligned} \xi ^{ad}(K^k_{n-k})=\left\{ \begin{array}{ll} \dfrac{n(n-1)^2}{2} &{} \mathrm{for} k=0, \\ \dfrac{1}{2}((n-k-1)^2(n-k)+(n-1)^2+2k) &{} \mathrm{for} k\ge 1. \end{array} \right. \end{aligned}$$

Proof

If $k=0$ then $K^k_{n-k}\cong K_{n-k}$ and $\xi ^{ad}(K^k_{n-k})=\dfrac{n(n-1)^2}{2}$. Since there are $n-k-1$ vertices of eccentricity 2 and the sum of degrees of its neighbors $((n-k-2)(n-k-1)+(n-1))$, one vertex of eccentricity 1 and the sum of degrees of its neighbors $(n-k-1)^2+k$, and k pendent vertices of eccentricity 2 and the sum of degrees of its neighbor $n-1$ in $K^k_{n-k}$, $k\ge 1$. Therefore, by Eq. (2), we obtain the following:

$$\begin{aligned} \begin{aligned} \xi ^{ad}(K^k_{n-k})&=\dfrac{(n-k-1)[(n-k-2)(n-k-1)+(n-1)]}{2}\\&\quad +\dfrac{(n-k-1)^2+k}{1}+\dfrac{k(n-1)}{2}\\&=\dfrac{1}{2}(n-k-1)^2(n-k-2+2)+\dfrac{1}{2}(n-1)(n-k-1+k)+k\\&=\dfrac{1}{2}((n-k-1)^2(n-k)+(n-1)^2+2k). \end{aligned} \end{aligned}$$

This completes the proof. $\square$

The following theorem gives the n-vertex-connected graph with larger eccentric adjacency index among all the graphs in ${\mathcal {G}}(n,k)$, where $0\le k\le n-1 (k\ne n-2)$.

Theorem 1

Let $G\in {\mathcal {G}}(n,k)$ be an n-vertex-connected graph with k cut edges. Then

$$\begin{aligned} \xi ^{ad}(G)\le \left\{ \begin{array}{ll} \dfrac{n(n-1)^2}{2} &{} \mathrm{for}\quad k=0, \\ \dfrac{1}{2}((n-k-1)^2(n-k)+(n-1)^2+2k) &{} \mathrm{for}\quad k\ge 1, \end{array} \right. \end{aligned}$$

equality hold if and only if $G\cong K^k_{n-k}$.

Proof

Let $G_{max}\in {\mathcal {G}}(n,k)$ be a graph with the largest eccentric adjacency index among all n-vertex-connected graphs with k cut edges. Let $E'=\{e_1,e_2,\ldots , e_k\}\subseteq E_{G_{max}}$ be the set of all cut edges of $G_{max}$. Then, all edges in $E'$ must be pendent edges and incident at a common vertex of $G_{max}$, say w. For $k=0$, the graph $G_{max}$ has no cut edges and its each component is a clique or a single vertex. If $G_{max}$ is not the graph as described above, then we can add an edge e between two non-adjacent vertices of $G_{max}$ and obtain a new graph $G_{max}+uv$ having no cut edges. But by Lemma 2, we get $\xi ^c(G_{max})<\xi ^c(G_{max}+uv)$ and it contradicts our assumption.

Therefore, now we have $1\le k\le n-1$ and $k\ne n-2$. If $G_{max}$ has an internal cut edge uv, then we can construct a new graph by identifying u with v and introducing a pendent edge uw with pendent vertex w and denote it by $G_2$. It is obvious that $G_2$ has k cut edges. Thus, by Lemma 3, we obtain $\xi ^c(G_{max})< \xi ^c(G_2)$, which is a contradiction. When $k=n-1$ we have $G_{max}$ is a tree, and thus, we have $G_{max}\cong S_n=K_{n-1}$, as our claim.

Next, we suppose that $1\le k\le n-3$. Now let 2-edge-connected graph $G_3$ with order $n-k$ and k pendent edges is an induced subgraph of $G_{max}$. If $G_3\ncong K_{n-k}$, then we can add edges into $G_3$. Similar to the above argument, we can deduce a new graph with a larger eccentric adjacency index than $G_{max}$, and therefore, $G_3\cong K_{n-k}$ in $G_{max}$. Moreover, we can conform that all k pendent edges in $G_{max}$ must be attached at the same vertex of $K_{n-k}$. Let $G_4\ncong G_{max}$ be a graph with k pendent edges and these vertices attached at $v_i$ vertices of $G_4$. Then, we can transform the k pendent edges to exactly one vertex of clique $K_{n-k}$ of $G_4$. Therefore, by Lemma 1, we construct a new graph with a larger eccentric adjacency index than that of $G_{max}$, which is a contradiction.

Therefore, from all the above discussion, we must have $G_{max}\cong K^k_{n-k}$. By Lemma 4, we have $\xi ^{ad}(K^k_{n-k})=\dfrac{n(n-1)^2}{2}$ for $k=0$, and $\xi ^{ad}(K^k_{n-k})=\dfrac{1}{2}((n-k-1)^2(n-k)+(n-1)^2+2k)$ for $k\ge 1$ and this completes the proof. $\square$

The following result is the consequence of Theorem 1 for $k=n-1$.

Theorem 2

(Akhter and Farooq [2]) Let G be an n-vertex-connected graph, $n\ge 2$. Then, $\xi ^{ad}(G)\le \dfrac{n^2-1}{2}$ with equality if and only if $G\cong S_n$.