On the first general Zagreb eccentricity index

1.   Introduction

All the graphs considered in the paper are simple, finite and undirected. A graph $G$ consists of two sets named as the set of vertices $V(G)$ and the set of edges $E(G)$. The number of elements in the vertex set is called the order and the number of edges in the edge set is called the size of the graph $G$. For a vertex $u\in V(G)$, $N_G(u)$ is the set of adjacent vertices with $u$ and is called the set of neighbors of $u$. The number of element in $N_G(u)$ is called the degree of the vertex $u$ in $G$ and is denoted by $d_G(u)$. For any graph with $n$ vertices, the vertex with degree $n-1$ is known as dominating vertex and the vertex with degree one is known as pendant vertex. The distance between the vertices $u$ and $w$, $d_G(u, w)$, is the length of the shortest path connecting them. A path whose length is equal to diameter is called diametrical path of $G$. For a vertex $u\in V(G)$, the maximum distance between the vertex $u$ and any other vertex of the graph $G$ is called the eccentricity of $u$ in $G$ and is denoted by $ec_G(u)$. A graph $G$ is said to be a bipartite graph of order $n$ if its vertex set can be partitioned into two disjoint vertex subsets, say $A$ and $B$, such that each edge of $G$ has one end in $A$ and other end in $B$. If $|A| = a$ and $|B| = b$, then $K_{a, b}$ represents the complete bipartite graph in which every vertex of $A$ is adjacent with vertex of $B$ by an edge. $P_n$ and $C_n$ denote the path and cycle graph on $n$ vertices. For other graph theoretical notations we refer ^[1].

Let $G$ and $H$ be two vertex disjoint graph, then the graph $G+H$ is obtained by joining each vertex of $G$ to each vertex of $H$ by an edge.

A topological index is a numerical quantity associated with a graph. Topological indices have many applications in chemistry, biology, pharmaceutics and other related fields. There are hundreds of degree, eccentricity and distance based topological indices have been introduced.

In 1972, Gutman et al. ^[2] introduced the first Zagreb index of a graph $G$ as

In 2005, Li and Zheng ^[3] generalized the definition of the first Zagreb index and proposed the first general Zagreb index by replacing the square by any non-zero real number $\gamma$,

In ^[4], the authors discussed the behavioral change in the first general Zagreb index for some graph operations, these operations involve edge moving, edge separating and edge switching in a graph. Liu et al. ^[5] studied the Cartesian product of two graphs, where one graph is D-sum and other graph is any connected graph. Bedratyuk and Savenko ^[6] expressed the general first Zagreb index in terms of the star sequence and the formulas of first general Zagreb index of certain cactus chains are discussed in ^[7].

In 2010, Todeschini and co-authors ^[8] proposed the multiplicative version of the first Zagreb index as

Recently, Vetrík et al. ^[9] introduced the first general multiplicative Zagreb index of a graph which is defined as

In ^[9], the authors proposed the extremal trees for the general multiplicative Zagreb index in terms of order, number of pendant vertices, segments and branching vertices. The same author investigated the extremal graphs with given clique number for the general multiplicative Zagreb index ^[10]. Recently in ^[11], authors found upper and lower bounds for the general multiplicative Zagreb index on the class of bicyclic, tricyclic and tetracyclic graphs.

Vuki$\check{c}$ević and Graovac replace the degree of the vertex with the eccentricity of the vertex and proposed the eccentricity based first Zagreb index as

The notation of the total eccentricity index is defined as the $\xi(G) = \sum_{u\in V(G)}ec(u)$.

In this paper, we introduce the generalized version of the first eccentricity Zagreb index. For any non-zero real number $\gamma$, the first general eccentricity Zagreb index of a graph $G$ is defined as

We investigate the extremal trees and bipartite graphs with respect to the first general Zagreb eccentricity index. Moreover, some bounds on the first general Zagreb eccentricity index are present in terms of order, size and the diameter of a graph. The presented results are for $\gamma > 0$, for $\gamma < 0$ results can be obtained on similar lines.

2.   Discussion and main results

In this section, we present some lemmas and our main results. Let $P_n$ and $S_n$ be the path and star with $n$ vertices. Assume $T_1$ be the tree with maximum degree $n-2$. From the definition of the first general Zagreb eccentricity index, we have the following formulas for $P_n$, $S_n$ and $T_1$.

Let $H$ be a tree as shown in Figure 1. The vertex $u$ has unique neighbor in $A$ and $C$ and $t\ge 1$ neighbors in $B$. Now we obtain a new graph $H'$ from the graph $H$ by switching these $t$ neighbors from $u$ to $v$.

Lemma 2.1. Let $H$ and $H'$ be the above defined graphs. Then for $\gamma > 0$

1. Let $P$ be a diametrical path of $H$ such that $E(P)\subseteq E(C)$. Then $E_1^{\gamma}(H) > E_1^{\gamma}(H')$,

2. If diametrical path $P$ contains the vertex $u$ and some vertices from $A$ and $C$ and $ec_H(u)\ge ec_H(v)$, then

Proof. Let $y$ be a pendant vertex of diametrical path $P$ and $x\in V(H)$ then $ec_H(x) = d_H(x, y)$. One can notice that for $x\in V(H)-V(B)$ we have $ec_{H}(x) = ec_{H'}(x)$, otherwise $ec_H(x)-ec_{H'}(x) = ec_{H}(u)-ec_{H'}(v) = ec_{H}(u)-ec_{H}(v)$. Moreover, for ($i$) and ($ii$) we have $ec_H(u) > ec_{H}(v)$ and $ec_H(u)\ge ec_{H}(v)$, respectively. Hence, $E_1^{\gamma}(H) > E_1^{\gamma}(H')$ and $E_1^{\gamma}(H)\ge E_1^{\gamma}(H')$ for $\gamma > 0$.

Let $\tau(n, k)$ contains all the trees of order $n$ with $k$ pendant vertices, where $2\le k\le n-1$.

Lemma 2.2. Let $G\in \tau(n, k)$, where $2\le k\le n-1$ such that $G$ has minimum first general Zagreb eccentricity index for $\gamma > 0$. Let $P = v_1v_2\cdots v_dv_{d+1}$ be a diametrical path in $G$. Then the vertices with degree at least three in G can only be the central vertices of $P$.

Proof. For $k$ = $2$ and $k$ = $n-1$, $\tau(n, k)$ contains only path and star graphs, respectively, hence the result is obvious. In the following we consider $3\le k\le n-2$.

Since $G$ has the minimum first general Zagreb eccentricity index for $\gamma > 0$, so from Lemma 2.1 we have information that no vertex of $G$ with degree at least three is outside $P$. Now we show that vertices with degree at least three on $P$ can only be the central vertices of $P$. Let $v_i$, $2\le i\le d$ and $d\ge 2$, be a vertex of $P$ with degree at least three. Let $ec_G(v_i) > ec_G(v_{i+1})$, then by applying Lemma 2.1 (ii) we can obtain a new tree in $\tau(n, k)$ with the smaller first general Zagreb eccentricity index for $\gamma > 0$, which is a contradiction. So, $ec_G(v_i)\le ec_G(v_{i+1})$. On similar lines we can get $ec_G(v_i)\le ec_G(v_{i-1})$. We have $ec_G(v_i) = d+1-i$ or $i$. For $ec_G(v_i)\le ec_G(v_{i+1})$, $i\le d+1-i\le i+1$ and this implies that $2i = d$ or $d+1$. For $ec_G(v_i)\le ec_G(v_{i-1})$, $i\ge d+1-i$ or $i\le d-i+2$ and this implies that $2i = d, d+1$ or $d+2$. Hence, $v_i$ is a central vertex of $P$.

Lemma 2.3. Let G be a tree in $\tau(n, k)$ with $3\le k\le n-2$. If G has unique vertex of degree at least three then for $\gamma > 0$, we have

and the equality holds for $G\cong T_{n, k}$.

Proof. Let $G\in \tau(n, k)$ has the minimum first general Zagreb eccentricity index for $\gamma > 0$ with unique vertex of degree at least three. This implies that there is a vertex $u\in V(G)$ having $k$ pendant paths. In these $k$ pendant paths, suppose that $P_a, P_b$ and $P_c$ be the maximum, second maximum and minimum length paths, i.e. $a\ge b\ge c$. Suppose that $uu_1\in E(G)$. For $a > b+1$, we have $ec_G(u) > ec_G(u_1)$ and by applying Lemma 2.1 we can construct a new tree satisfying the given condition with the smaller first general Zagreb eccentricity index for $\gamma > 0$, which is a contradiction. So we have either $a = b$ or $b+1$. Now let $a > c+1$. Suppose that $u'$ and $u''$ be the pendant vertices of $P_1$ and $P_3$ and $u'w\in E(P_1)$. We attained a new graph $G^* = G-u'w+u'u''$. Clearly, $G^*$ has unique vertex of degree at least three. Hence, we obtain $ec_{G^*}(v)\le ec_{G^*}(v)$ for all vertices of $G$, which again leads to a contradiction. Thus either $a = c$ or $a = c+1$, in other words we have $G\cong T_{n, k}$.

In the following result, we characterize the extremal trees with the maximum and minimum first general Zagreb eccentricity index.

Theorem 2.1. Let T be a tree of order n, then for $\gamma > 0$

and for $\gamma\ge 1$

the equalities in (1) and (2) hold for path and star graphs, respectively, of order $n$.

Proof. If $T$ is a path of order $n$, then we have nothing to prove. Let $T\ncong P_n$ be a tree with the diameter $d$ and $P_{d+1} = u_1u_2\cdots u_du_{d+1}$ be the longest path in $T$. This implies that $ec_T(u) = max\{d_T(u, u_1), d_T(u, u_{d+1})\}\le d$, for each $u\in V(T)$. Since $T$ is a tree so $u_1$ and $u_{d+1}$ must be pendant vertices. Moreover, $T\ncong P_n$ so there is at least one more pendant vertex, say $v$, and $vw\in E(G)$. Now we obtain a new tree $T'$ from $T$ as $T' = T-vw+vu_{d+1}$. Clearly, $T'$ has diameter $d+1$ with the longest path $u_1u_2\cdots u_du_{d+1}v$. This implies that for $u\ne v$ we have $ec_{T'}(u) = max\{d_{T'}(u, u_1), d_{T'}(u, v)\} = max\{d_T(u, u_1), d_T(u, u_{d+1})+1\}\ge max\{d_T(u, u_1), d_T(u, u_{d+1})\} = ec_T(u)$ and for $ec_{T'}(v) = d+1 > d\ge ec_{T}(v)$. From the definition of the first general Zagreb eccentricity index and the construction of $T'$ we have $E_1^{\gamma}(T) < E_1^{\gamma}(T')$, i.e. this construction increases the $E_1^{\gamma}$ for $\gamma > 0$. Now, if $T\cong P_n$ then we are done, otherwise there exist at least one pendant vertex, say $v'\ne u_1, u_{d+1}$, and we will repeat the construction. After finite number of repetition, we obtain a tree with maximum degree two and every repetition increases $E_1^{\gamma}$, hence $P_n$ gives the maximum $E_1^{\gamma}$ for $\gamma > 0$.

Now we will work for the lower bound. If $T$ is $S_n$, then we have nothing to prove and for $T\cong T_1$ the inequality is strict. Now we suppose that $T\ncong S_n$ and $T\ncong T_1$. Let $d$ be the diameter of $T$ and $P_{d+1} = u_1u_2\cdots u_du_{d+1}$ be a longest path in $T$. Suppose that $d(u_2)\ge d(u_d)$. Choose $v$ an arbitrary maximum degree vertex, unless $u_d$ has maximum degree, in which case $v$ is chosen to be $u_2$. We obtain a new tree $T''$ such that $T'' = T-u_du_{d+1}+u_{d+1}v$. This implies that $ec_{T'}(u) = max\{d_{T'}(u, u_1), d_{T'}(u, u_d)\} = max\{d_T(u, u_1), d_T(u, u_{d+1})-1\}\le max\{d_T(u, u_1), d_T(u, u_{d+1})\} = ec_T(u)$. From this we obtain that $E_1^{\gamma}(T)\ge E_1^{\gamma}(T')$, i.e., this construction provides a non-decreased value of $E_1^{\gamma}$ for $\gamma\ge 1$. If $T''\cong T_1$, the proof is complete. Otherwise, we will continue the construction as follows; we choose a pendant vertex from a longest path whose neighbor does not have the maximum degree. Now we obtain a new graph by deleting that pendant edge and joining this to the maximum degree vertex. After finite number of repetition we obtain a graph with maximum degree $n-2$, i.e. $T_1$ graph. Hence the required result.

From the above result, we have the following corollaries for the first Zagreb eccentricity and the total eccentricity indices.

Corollary 2.1. For a tree of order n, the total eccentricity and the first Zagreb indices are given as

in above both left equalities hold for the star of order $n$ while the right equalities hold for the path of order $n$.

Let $K_{n-2r-2, 2}$ be the complete bipartite graph of order $n-2r$, then we obtain a graph $G_1$ from $K_{n-2r-2, 2}$ by joining the vertices of degree $n-2r-2$ of $K_{n-2r-2, 2}$ by an edge and attaching two paths $P_{q+1}$ with each of them, i.e. $G_1 = K_{n-2r-2, 2}+uv+uw_{r+1}w_{r}\cdots w_{1}+vw_{r+2}w_{r+3}\cdots w_{2r+2}$ where $u$ and $v$ are the vertices of degree $n-2r-2$ in $K_{n-2r-2, 2}$.

Let $G_2$ be a graph of order $n$ obtained from $K_{n-2r-1, 2}$ by joining a new vertex $w$ to the two vertices of $K_{n-2r-1, 2}$ of degree $n-2r-1$ and attaching two paths $P_r$ with each of them, i.e. $G_2 = K_{n-2r-1, 2}+uw+vw+uw_rw_{r-1}\cdots w_2w_1+vw_{r+1}w_{r+2}\cdots w_{2r}$. The above discussed graphs $G_1$ and $G_2$ are shown in Figure 2.

Now let, $\tau_i$, $i = 1, 2$, be the collection of all graphs $H_i = (V, E)$ with diameter $d = 2r+i$ such that $V(G_i) = V(H_i)$ and $E(G_i)\subseteq E(H_i)$.

The following result provides the lower bound on the first general Zagreb eccentricity index involving the number of vertices and the diameter of a graph.

Theorem 2.2. For a graph G with vertices n and diameter d, we have

and the equality holds if and only if $G\cong P_n$ or $G\in \tau_i$ for $i = 1, 2$.

Proof. Let $P_{d+1} = w_1w_2\cdots w_{d+1}$ be the longest path in $G$. Also, $n\ge d+1$ and $ec(u)\ge \lceil \frac{d}{2} \rceil$ for every $u\in V(G)$. Clearly, for $n = d+1$ we have $G\cong P_n$ and the equality holds. Now let $n > d+1$ and we have

From the definition of $E_1^{\gamma}$ we have

Now conversely suppose that equality hold in the result for $n > d+1$, then from Eq. 2.4 we get $ec(u) = \lceil \frac{d}{2}\rceil$ for each $u\in V(G)$. This implies that all the vertices $w_j$, $d+2\le j\le n$, are adjacent with $w_r$ and $w_{r+2}$ for $d = 2r$ and for $d = 2r+1$ vertices $w_j$, $d+2\le j\le n$, are adjacent with $w_{r+1}$ and $w_{r+2}$ and hence $G\in \tau_i$, i = 1, 2.

Now, we have the following direct result.

Corollary 2.2. Let $G$ be a graph of order n and diameter d. Then for the total eccentcity and first eccentricity Zagreb indices we have

both equalities hold if and only if $G\cong P_n$ or $G\in \tau_i$ for $i = 1, 2$.

The following theorem characterizes the extremal bipartite graphs with respect to the first general Zagreb eccentricity index.

Theorem 2.3. Let G be a bipartite graph of order n. For $\gamma > 0$, we have

and the left and right equalities hold for $K_{a, b}$ and $P_n$, respectively, where $a+b = n$.

Proof. If $G\cong K_{a, b}$, we have nothing to prove. Suppose that $G\ncong K_{a, b}$. Clearly, $G$ can be obtained from $K_{a, b}$ by removing some edges. From the definition of the first general Zagreb eccentricity index we have $E_1^{\gamma}(G)\ge E_1^{\gamma}(K_{a, b}-e) > E_1^{\gamma}(K_{a, b})$ for $\gamma > 0$.

For upper bound, if $T$ is a spanning tree of a bipartite graph $G$, then $E_1^{\gamma}(G)\le E_1^{\gamma}(T)\le E_1^{\gamma}(P_n)$, the last inequality is due to the Theorem 2.1.

The next results can be obtained easily from the above result.

Corollary 2.3. For a bipartite graph G of order n, the total eccentricity and the first Zagreb indices is given as

both the equalities on the left and right hand sides hold for $K_{a, b}$ and $P_n$, respectively, where $a+b = n$.

Let $n, m$ and $q$ be positive integers such that $n-1\le m\le \left(\begin{array}{l} n\\ 2 \end{array} \right)$ and $t = \left\lfloor {\frac{{2n - 1 - \sqrt {{{\left({2n - 1} \right)}^2} - 8m} }}{2}} \right\rfloor$. Let $X$ be a graph of order $n-t$ and size $m-\left(\begin{array}{l} n\\ 2 \end{array} \right)-t(n-t)$, and $G(n, m)$ be the set of $K_t+X$ graphs. We can notice that $t$, $1\le t < n$ is the greatest integer fulfilling $2m\ge t(n-1)+t(n-t)$ or $f(t) = t^2-2nt+t+2m$, we have $\left[m- \left(\begin{array}{l} n\\ 2 \end{array} \right)-t(n-t)\right]-(n-t-1) = \frac{1}{2}f(t+1) < 0$. This gives that each vertex of $X$ has eccentricity two in $K_t+X$.

Theorem 2.4. Let G be a graph of order n and size m and $(n-1)\le m < \left(\begin{array}{l} n\\ 2 \end{array} \right)$, then for $\gamma > 0$

and the equality holds if and only if $G\in G(n, m)$.

Proof. Let $c$, $0\le c\le n-2$, be the number of dominating vertices in $G$. Clearly, for $c = 0$ we have $E_1^{\gamma}(G)\ge n\cdot 2^{\gamma} > n\cdot 2^{\gamma}-3t$. Now suppose that $c\ge 1$, this implies that $n-c$ non-dominating vertices have eccentricity two in $G$, thus $E_1^{\gamma}(G) = (n-c)\cdot 2^{\gamma}+c$. Since $t$ is the largest integer fulfilling the inequality $2m\ge t(n-1)+t(n-t)$ which implies that $c\le t$. Moreover, $(n-c)\cdot 2^{\gamma}+c$ is a decreasing function with respect to $c$ for $\gamma > 0$. Thus we have the result $E_1^{\gamma}(G) = (n-c)\cdot 2^{\gamma}+c\ge (n-t)\cdot 2^{\gamma}+t$ and the equality holds if and only if $G$ contain exactly $t$ dominating vertices and $n-t$ vertices with eccentricity two, i.e. $G$ is a graph from $G(n, m)$.

Corollary 2.4. Let G be a graph of order n and size m and $(n-1)\le m < \left(\begin{array}{l} n\\ 2 \end{array} \right)$, then we have

and the equalities hold if and only if $G\in G(n, m)$.

For positive integers $n$ and $k$ with $3\le k\le n-2$, suppose $s = \lfloor \frac{n-1}{k}\rfloor$ and $t = n-1-ks$. Let $T_{n, k}$ be a tree obtained by attaching $k-t$ paths of $s$ vertices and $t$ paths of $s+1$ vertices to a common vertex. If $n-2\ \equiv 0(mod\, \, k)$. then $T^{n, k}(q)$ be a tree obtained by attaching $q$ and $k-q$ path of $\frac{n-2}{k}$ vertices, respectively, to the two end vertices of an edge, where $1\le q\le \lfloor \frac{k}{2} \rfloor$. These graphs are shown in Figure 3.

Theorem 2.5. For $n\ge 4$ and $3\le k\le n-2$, let $G\in \tau(n, k)$, $s = \lfloor \frac{n-1}{k}\rfloor$ and $t = n-1-ks$. For $\gamma \ge 1$, we have

and the equality in above holds if and only if $G\cong T_{n, k}$ or $G\cong T^{n, k}$ with $2\le q\le \lfloor \frac{k}{2}\rfloor$ when $n-2\equiv 0(mod \, \, k)$.

Proof. Let $G$ be a graph in $\tau(n, k)$ having the minimum first general Zagreb eccentricity index. Denoting $V_3(G)$ the set of vertices in $G$ of degree at least three. Lemma 2.2 implies that either $|V_3(G)| = 1$ or $|V_3(G)| = 2$. If $|V_3(G)| = 1$, then result follows from Lemma 2.3. Now consider that $|V_3(G)| = 2$ and $V_3(G) = \{u_1, u_2\}$. Let $P$ be a diametrical path in $G$, then from Lemma 2.2 $u_1u_2\in E(P)$ and $ec_G(u_1) = ec_(u_2)$. Let $a$ and $b$ be the maximum and minimum length of pendant paths at $u_1$ and $a > b$. Let $H$ be the graph obtained from $G$ by shifting all the neighbors of $u_1$ in $G$ outside $P$ to $u_2$, then by Lemma 2.1 (ii) we have $E_1^{\gamma}(G) = E_1^{\gamma}(H)$. Note that $|V_3(H)| = 1$ and in $H$ there are two pendant paths of lengths $a+1$ and $b$ on $u_2$. As $a-b+1 > 1$, we have $E_1^{\gamma}(G) = E_1^{\gamma}(H) > E_1^{\gamma}(T_{n, k})$, which is a contradiction. Hences, all pendant paths on $u_1$ have the same length in $G$. Similarly, we can show that each pendant paths at $v$ have the same length. This implies that $G\cong T^{n, k}(q)$ with $2\le q\le \lfloor \frac{k}{2}\rfloor$.

Corollary 2.5. For $n\ge 4$ and $3\le k\le n-2$, let $G\in \tau(n, k)$, $s = \lfloor \frac{n-1}{k}\rfloor$ and $t = n-1-ks$. Then the total eccentricity index of $G$ is

equality in above holds if and only if $G\cong T_{n, k}$ or $G\cong T^{n, k}$ with $2\le q\le \lfloor \frac{k}{2}\rfloor$ when $n-2\equiv 0(mod \, \, k)$.

Corollary 2.6. For $n\ge 4$ and $3\le k\le n-2$, let $G\in \tau(n, k)$, $s = \lfloor \frac{n-1}{k}\rfloor$ and $t = n-1-ks$, then the first Zagreb eccentricity index

equality holds if and only if $G\cong T_{n, k}$ or $G\cong T^{n, k}$ with $2\le q\le \lfloor \frac{k}{2}\rfloor$ when $n-2\equiv 0(mod \, \, k)$.

Let $T_{n, q, p}$ be a tree of order $n$ attained by attaching $p$ and $q-p$ pendant vertices to the two pendant vertices of $P_{n-q}$, where $1\ge p\ge \lfloor \frac{q}{2}\rfloor$. Let $\tau ^{n, q}$ be the set of all $T_{n, p, q}$ trees.

Theorem 2.6. Let $G\in \tau(n, k)$, where $2\le k\le n-1$, then for $\gamma\ge 1$ we have

the equality holds if and only if $G\in \tau^{n, q}$.

Proof. If $d$ is the diameter of $G$, then diametrical path $P$ of $G$ contain $d-1$ non-pendant vertices thus $k\le n-(d-1)$, i.e. $d\le n-k+1$. From Theorem 2.2, we have $E_1^{\gamma}(G)\le \phi(n, d)\le \phi(n, n-k+1)$. Clearly, $E_1^{\gamma}(G) = \phi(n, n-k+1)$ if and only if $G\in \tau ^{n, k}$.

Corollary 2.7. Let $G\in \tau(n, k)$, where $2\le k\le n-1$, then for $\gamma\ge 1$ we have

the equality holds if and only if $G\in \tau^{n, q}$.

Corollary 2.8. Let $G\in \tau(n, k)$, where $2\le k\le n-1$, then for $\gamma\ge 1$ we have

the equality holds if and only if $G\in \tau^{n, q}$.

3.   Conclusions

The generalized version of the first Zagreb eccentricity index is proposed in this paper. The classes of trees and bipartite graphs are chosen to find the extremal graphs for the first general Zagreb eccentricity index. Some bounds of the index is also proposed in terms of the number of vertices, number of edges and diameter. In each case extremal graphs are determined.

Acknowledgements

This research is supported by the UPAR Grants of United Arab Emirates University via Grant No. G00002590 and G00003271.

Conflict of interest

All authors declare no conflicts of interest in this paper.