Open AccessArticle

Bounds on the General Eccentric Connectivity Index

Xinhong Yu

¹,

Muhammad Imran

^2,*

Aisha Javed

³,

Muhammad Kamran Jamil

⁴ and

Xuewu Zuo

⁵

Basic Course Teaching Department, Hefei University of Economics, Hefei 230013, China

Department of Mathematical Sciences, College of Science, United Arab Emirates University, Al Ain 15551, Abu Dhabi, United Arab Emirates

Abdus Salam School of Mathematical Sciences, Government College University, Lahore 54600, Pakistan

⁴

Department of Mathematics, Riphah Institute of Computing and Applied Sciences, Riphah International University, Lahore 46000, Pakistan

⁵

Department of Mathematics, Ministry of General Education, Anhui Xinhua University, Hefei 230013, China

Author to whom correspondence should be addressed.

Symmetry 2022, 14(12), 2560; https://doi.org/10.3390/sym14122560

Submission received: 11 October 2022 / Revised: 18 November 2022 / Accepted: 22 November 2022 / Published: 4 December 2022

(This article belongs to the Special Issue Combinatorics, Discrete Mathematics, Symmetry and Regularity in Graphs, Graph Indices, Graph Parameters and Applications of Graph Theory)

Download Versions Notes

Abstract

The general eccentric connectivity index of a graph R is defined as

ξ^{e c} (R) = \sum_{u \in V (G)} d (u) e c {(u)}^{α}

, where

α

is any real number,

e c (u)

and

d (u)

represent the eccentricity and the degree of the vertex u in R, respectively. In this paper, some bounds on the general eccentric connectivity index are proposed in terms of graph-theoretic parameters, namely, order, radius, independence number, eccentricity, pendent vertices and cut edges. Moreover, extremal graphs are characterized by these bounds.

Keywords:

eccentricity of vertex; eccentric connectivity index; general eccentric connectivity index; extremal graphs

MSC:

05C07; 05C35; 05C69

1. Introduction

For terminologies and notations in graph theory that are not defined here, we refer to [1]. All considered graphs in this paper are finite, connected, and simple. A graph R is an ordered pair

R = (F, M)

. Here, F and M constitute the set of vertices and the set of edges, respectively. Cardinalities of these sets

| F |

and

| M |

are called the order and the size of the graph R. The neighborhood of a vertex u is the set of its adjacent vertices, and the cardinality of this set is said to be the degree of u. The degree of u in R is denoted as

d_{R} (u)

. A vertex u is called a pendant vertex if

d (u) = 1

. The length of any shortest path between the vertices u and v is called the distance between them and is denoted as

d_{R} (u, v)

. The maximum distance between the vertex u and any other vertex of R is called the eccentricity,

e c_{R} (u)

, of u in R. The maximum and the minimum eccentricity of any vertex among all vertices of the graph R is known as the diameter and the radius of R. The cardinality of the largest independent set of R is called the independence number of R and the minimum number of vertices whose removal from R generates a disconnected graph is called the connectivity of R. The complement of a graph R is a graph

\bar{R}

with the same vertex set and two vertices are adjacent if and only if they are non-adjacent in R. For two graphs G and H,

G + H

is the join graph of G and H whose vertex set is the vertices of G and H and the edge set consist of all the edges of G and H with all edges connecting each vertex of G with each vertex of H. Path, Star and complete graphs of order n are denoted by

P_{n}, S_{n}

and

K_{n}

Chemical graph theory is a branch of mathematical chemistry that deals with the nontrivial applications of graph theory to clear up molecular issues. In standard, a graph is used to represent a molecule with the aid of thinking about the atoms of the vertices of the graph and the molecular bonds as the edges. Then, the principal goal is to use algebraic invariants to reduce the topological structure of a molecule to a single quantity that could generate the same residences of the molecule. This single number is known as a

topological index

The

eccentric connectivity index

of R [2], is defined as

ξ^{e c} (R) = \sum_{u \in V (R)} e c_{R} (u) d_{R} (u) .

This index has been considered for some classes of graphs. Zhou and Du [3] and Morgan et al. [4] independently investigated the sharp lower bound for the eccentric connectivity index of trees with given order and diameter. Morgan et al. [5] inveterate the sharp lower bound for the eccentric connectivity index of a connected graph with a given diameter. Recent results on the eccentric connectivity index of graphs can be seen in [2,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21] and the references therein.

The authors in [22] introduced the general version of the eccentric connectivity index, namely the general eccentric connectivity index (GECI). For any real number

α

, GECI of graph R is defined as

ξ_{α}^{e c} (R) = \sum_{u \in V (R)} d_{R} (u) e c_{R} {(u)}^{α} .

For

α = 1

we obtain the classic eccentric connectivity index. The authors in [22] worked for trees and unicyclic graphs and put some bounds on these classes of graphs in terms of the order, diameter and pendant vertices for

α > 0

2. Main Results

In this section, some lemmas and the main results of the paper are presented. In a graph, R adding an edge by joining two non-adjacent vertices increases the degrees and may decrease the eccentricity of the vertices. The following lemma tells that adding an edge in R increases the general eccentric connectivity index (GECI).

Lemma 1.

Let u and v be non-adjacent vertices in R, then for

α < 0

ξ_{α}^{e c} (R) < ξ_{α}^{e c} (R + u v) .

Proof.

From the definition of the general eccentric connectivity index for

α < 0

, we have,

ξ_{α}^{e c} (R) - ξ_{α}^{e c} (R + u v) \leq e c {(u)}^{α} (d (u) - d (u) - 1) + e c {(v)}^{α} (d (v) - d (v) - 1) < 0

. □

The following result gives the upper bound on GECI for R in terms of the order of R.

Theorem 1.

Let R be a connected simple graph on r vertices and m edges, then for

α < 0

ξ_{α}^{e c} (R) \leq 2 m \leq r (r - 1)

equality holds if and only if

R ≅ K_{r}

Proof.

Since

e c (u) \geq 1

for all

u \in V (R)

, so

ξ_{α}^{e c} (R) = \sum_{u \in V (R)} d (u) e c {(u)}^{α} \leq \sum_{u \in V (R)} d (u) = 2 m \leq r (r - 1)

equality holds if and only if every vertex of R has eccentricity one, i.e.,

R = K_{n}

. □

Let

r_{1}

represent the number of vertices with the eccentricity one in R. Let

K_{n} - q e

be the graph achieved from

K_{n}

by removing q independent edges for

0 \leq q \leq ⌊ \frac{r}{2} ⌋

Theorem 2.

Let R be a connected graph of order r with

r_{1} ⩾ 1

number of vertices with eccentricity one and for

α < 0

, we have

ξ_{α}^{e c} (R) \leq r 2^{α} (r - 2) + r_{1} (r - 1 - (r - 2) 2^{α})

and the equality holds if and only if

R = K_{r_{1}} + (K_{r - n r_{1}} - \frac{r - r_{1}}{2} e)

, where

r - r_{1}

is even.

Proof.

Let

E_{1} = {u; e c (u) = 1, u \in V (G)}

, then for

w \in V (R) ∖ E_{1}

, we have

e c (w) \geq 2

it follows that

d (w) \leq r - 2

. Now

\begin{matrix} ξ_{α}^{e c} (R) & = \sum_{u \in E_{1}} d (u) e c {(u)}^{α} + \sum_{w \in V (R ∖ E_{1})} d (w) e c {(w)}^{α} \\ \leq r_{1} (r - 1) + \sum_{w \in V (R ∖ E_{1})} (r - 2) 2^{α} \\ = r_{1} (r - 1) + (r - r_{1}) (r - 2) 2^{α} \\ = r_{1} (r - 1 - (r - 2) 2^{α}) + r (r - 2) 2^{α} \end{matrix}

and the equality holds if and only if

e c (w) = 2

and

d (w) = r - 2

for any

w \in V (R) ∖ E_{1}

. Hence, the required result. □

Theorem 3.

Let R be a connected graph of order r and size m. Let

a = ⌊\frac{2 r - 1 - \sqrt{{(2 r - 1)}^{2} - 8 m}}{2}⌋

be the greatest integer satisfying that

y^{2} + (1 - 2 r) y + 2 m \geq 0

. Then, for

α < 0

, we have

ξ_{α}^{e c} (R) \leq \frac{r (r - 2)}{2} + \frac{r}{2} a

and the equality holds if and only if

R = K_{a} + (K_{r - a} - \frac{r - a}{2} e)

, where

r - a

is even.

Proof.

From Theorem 2, we know that

ξ_{α}^{e c} (R) \leq r_{1} (r - 1 - (r - 2) 2^{α}) + r (r - 2) 2^{α}

. Moreover,

2 m = \sum_{w \in V (R)} \geq r_{1} (r - 1) + r_{1} (r - r_{1})

this implies that

r_{1} \leq a

. So,

ξ_{α}^{e c} (R) \leq r_{1} (r - 1 - (r - 2) 2^{α}) + r (r - 2) 2^{α} \leq a (r - 1 - (r - 2) 2^{α}) + r (r - 2) 2^{α}

and the equality holds if and only if R has exactly a vertices with eccentricity one and rest of vertices having degree two. □

Theorem 4.

Let R be a graph of order r and radius h. Then, for

α < 0

ξ_{α}^{e c} (R) \leq r (r - h) h^{α}

and the equality holds if and only if either

R = K_{r}

R = K_{r} - \frac{r}{2} e

for even n.

Proof.

For any

u \in V (R)

, we know that

d (u) \leq r - e c (u)

. Then, for

α < 0

, we have

ξ_{α}^{e c} (R) = \sum_{u \in V (R)} d (u) e c {(u)}^{α} \leq \sum_{u \in V (R)} (r - e c (u)) e c {(u)}^{α} \leq r (r - h) h^{α}

. Function

f (x) = (r - x) x^{α}

is a decreasing function as

f^{'} (x) < 0

for

α < 0

and

r > x

. The equalities in the above hold when

e c (u) = r - d (u)

and

e c (u) = h

for every vertex of R, i.e., G is an

r - h

regular graph with

e c (u) = h

for any vertex u of R. This follows that either

R = K_{r}

R = K_{r} - \frac{r}{2} e

for even

r

. □

Let

R_{1}

and

R_{2}

be two graphs obtained from

K_{r - γ} + \bar{K_{γ}}

by removing an edge joining two vertices in

K_{r - γ}

and

\bar{K_{γ}}

and removing an edge incident two vertices in

K_{r - γ}

, respectively.

Theorem 5.

Let R be a graph with order

r > 5

having independence number γ. Then, for

α < 0

, we have

i.: $ξ_{α}^{e c} (R) \leq (r - γ) (r - 1) + γ (r - γ) 2^{α}$ and the equality holds if and only if $R = K_{r - γ} + \bar{K_{γ}}$ ,
ii.: $ξ_{α}^{e c} (R) \leq (r + γ - 1) (r - 1) + (r - 2) 2^{α} + (r - γ - 1) 2^{α} + (γ - 1) (r - γ) 2^{α}$ and the equality holds if and only if $R = R_{1}$ .

Proof.

From Lemma 1, we know that for

α < 0

, adding an edge between two non-adjacent vertices of G increases the GECI.

K_{r - γ} + \bar{K_{γ}}

has the maximum number of edges with independent number

γ

, this implies that (i)

ξ_{α}^{e c} (R) \leq (r - γ) (r - 1) + γ (r - γ) 2^{α}

For (ii), whenever we remove an edge e from

K_{r - γ} + \bar{K_{γ}}

we always obtain either

R_{1}

R_{2}

. Moreover,

ξ_{α}^{e c} (R_{1}) = (r + γ - 1) (r - 1) + (r - 2) 2^{α} + (r - γ - 1) 2^{α} + (γ - 1) (r - γ) 2^{α}

and

ξ_{α}^{e c} (R_{2}) = (r - γ - 2) (r - 1) + 2 (r - 2) 2^{α} + γ (n - γ) 2^{α}

. Lemma 1 implies that in order to obtain the result we only need to compare the GECI of

R_{1}

and

R_{2}

for

α < 0

, which is

ξ_{α}^{e c} (R_{1}) - ξ_{α}^{e c} (R_{2}) = (r - 1) (1 - 2^{α}) > 0

, which is the required result. □

Let

λ

denote the covering number of R, since

γ (R) + λ (R) = r

then we have the following corollary.

Corollary 1.

Let R be a graph of order r and covering number λ, then for

α < 0

, we have

ξ_{α}^{e c} (R) \leq λ {(r - 1 + \frac{r - λ}{2})}^{α}

and the equality holds if and only if

R = K_{λ} + \bar{K_{r - λ}}

Theorem 6.

Let R be graph of order n and connectivity κ, then for

α < 0

, we have

ξ_{α}^{e c} (R) \leq 2^{α} (r^{2} - r (3 + κ) + 3 κ + 2) + κ (r - 1)

and the equality holds if and only if

R = (K_{1} ⋃ K_{r - κ - 1}) + K_{κ}

Proof.

For

α < 0

, let

R^{'}

be a graph with maximum

ξ_{α}^{e c}

among all graphs of order n and connectivity

κ

. Then, there is a set of vertices C with cardinality

κ

such that

R^{'} - C = ⋃_{i}^{p} R_{i}

, where

p \geq 2

and

R_{i}

’s are the connected components of

R - C

. By Lemma 1 adding edges increases the

ξ_{α}^{e c}

for

α < 0

, so R must be like

R^{'} = (K_{r_{1}} ⋃ K_{r_{2}}) + K_{κ}

such that

r_{1} + r_{2} = r - κ

and without loss of generality suppose

r_{1} \leq r_{2}

. Now,

\begin{matrix} ξ_{α}^{e c} (R^{'}) & = \sum_{u \in V (K_{r_{1}})} d (u) e c {(u)}^{α} + \sum_{u \in V (K_{r_{2}})} d (u) e c {(u)}^{α} + \sum_{u \in V (K_{κ})} d (u) e c {(u)}^{α} \\ = r_{1} (r_{1} + κ - 1) 2^{α} + r_{2} (r_{2} + κ - 1) 2^{α} + k (r - 1) \\ = 2^{α} (r - κ) (r - 1) - 2^{α + 1} r_{1} r_{2} + κ (r - 1) \\ \leq 2^{α} (r - κ) (r - 1) - 2^{α + 1} (r - κ - 1) + κ (r - 1) \\ = 2^{α} (r^{2} - r (3 + κ) + 3 κ + 2) + κ (r - 1) \end{matrix}

and equality holds if and only if

r_{1} = 1

and

r_{2} = r - κ - 1

. □

For edge connectivity and minimum degree, we have a famous relation

κ (R) \leq κ^{'} (R) \leq δ (R)

. Let

ϕ (x) = 2^{α} (r^{2} - r (3 + x) + 3 x + 2) + x (r - 1)

, then

ϕ^{'} (x) > 0

for

α < 0

this implies that

ϕ (x)

is an increasing function for

r > x > 0

so we have

ϕ (κ) \leq ϕ (κ^{'}) \leq ϕ (δ)

. This gives the following given results.

Corollary 2.

Let R be a graph of order n and edge-connectivity

κ^{'}

, then for

α < 0

we have

ξ_{α}^{e c} (R) \leq 2^{α} (r^{2} - r (3 + κ^{'}) + 3 κ^{'} + 2) + κ^{'} (r - 1)

and the equality holds if and only if

R = (K_{1} ⋃ K_{r - κ^{'} - 1}) + K_{κ^{'}}

Corollary 3.

Let R be a graph of order n with minimum degree δ, then for

α < 0

, we have

r δ {(r - δ)}^{α} \leq ξ_{α}^{e c} (R) \leq 2^{α} (r^{2} - r (3 + δ) + 3 δ + 2) + δ (r - 1)

the left equality holds if and only if either

R = K_{r}

R = K_{r} - \frac{r}{2} e

for even n and the right equality holds if and only if

R = (K_{1} ⋃ K_{r - δ - 1}) + K_{δ}

Proof.

Since

d (u) \geq δ

for every

u \in V (R)

from Theorem 4 we know that

f (x)

is a decreasing function, we have

\begin{matrix} ξ_{α}^{e c} (R) \geq \sum_{u \in V (R)} d (u) {(r - d (u))}^{α} \geq \sum_{u \in V (R)} δ {(r - δ)}^{α} = r δ {(r - δ)}^{α} . \end{matrix}

□

Let

K_{r}^{t}

be a graph obtained from

K_{r - t}

by joining t pendant vertices to one vertex of

K_{r - t}

. Let

⊤_{r}^{t}

be the set of all trees achieved by identifying both end vertices of

P_{r - t}

with the centers of

S_{p + 1}

and

S_{q + 1}

, respectively, where

p, q \geq 0

and

p + q = k

. One can notice that

ξ_{α}^{e c} (R) = ξ_{α}^{e c} (H)

for every pair of graphs

R, H \in ⊤_{r}^{t}

. Let

A (k)

be the k-th harmonic number, i.e.,

A (k) = 1 + \frac{1}{2} + \dots + \frac{1}{k}

Theorem 7.

Let R be a graph of order r with t pendant vertices, for

α < 0

, we have

λ \leq ξ_{α}^{e c} (R) \leq 2^{α} ({(r - t - 1)}^{2} + t) + r - 1

where

λ = \{\begin{matrix} t {(r - t + 1)}^{α} + (t + 2) {(r - t)}^{α} + 4 A (r - t - 1) - 4 A (\frac{r - t}{2}); \\ w h e n r - t i s e v e n \\ (t + 2^{1 - α}) {(r - t + 1)}^{α} + (t + 2) {(r - t)}^{α} + 4 A (r - t - 1) - 4 A (\frac{r - t + 1}{2}); \\ w h e n r - t i s o d d \end{matrix}

and the upper bound achieved if and only if

R = K_{r}^{t}

and lower bound is achieved if and only if

R \in ⊤_{r}^{t}

Proof.

Let R have the maximum GECI among all graphs of order r with t pendant vertices. Let

{u_{1}, u_{2}, \dots, u_{t}}

be pendant vertices of R, then by Lemma 1

V (R) ∖ {u_{1}, u_{2}, \dots, u_{t}}

induces a complete graph H. Now, all the pendant vertices are adjacent to some vertices of H. Now our next goal is to show that

R = K_{r}^{t}

Suppose that u and v are the only vertices of R such that

d (u) \geq d (v) > r - t - 1

. A new graph

R^{'}

is achieved from R by shifting all pendant vertices from v to u. It is easy to see that for any

w \in V (R) ∖ {u}

, we have

e c_{R} (w) = e c_{R^{'}} (w)

e c_{R} (u) > e c_{R^{'}} (u)

and

e c_{R^{'}} (w) = e c_{R} (w) - 1

for any pendant vertex w. The degrees of vertices in

V (R) ∖ {u, v}

remain the same, and the degree of u increases by

d_{R} (v) - r + t + 1

and the degree of v decreases by

d_{R} (v) - r - t + 1

Now, we compare the GECI values of R and

R^{'}

for

α < 0

as which is a contradiction against the supposition that R has maximum GECI. Now, consider that H contains at least two vertices of degrees at least

r - t

. By repeating the above procedure we can obtain a graph with a larger GECI, which is again a contradiction. Hence,

R = K_{r}^{t}

Now, for the lower bound, suppose that K is the graph with minimum GECI among all graphs of order n and t pendant vertices. Lemma 1 tells that K must be a tree. Further, we need to prove that

K \in ⊤_{r}^{t}

Claim 1.

must be a caterpillar.

Proof of Claim 1:

Let

P_{s + 1} = u_{0} u_{1} u_{2} \dots u_{s}

be a longest path in K. We consider

s \geq 4

because

s = 3

is a caterpillar. Suppose that

j \in {2, 3, \dots, ⌊ \frac{t + 1}{2} ⌋}

is the smallest integer such that there is a vertex w different from

u_{i - 1}

and

u_{i + 1}

which is adjacent to

u_{i}

. Let

N_{R} (w) = {u_{i}, w_{1}, w_{2}, \dots, w_{q}}

, where

q \geq 2

. Let

T_{1}

be the subtree of

K - u_{i} u_{i + 1} - u_{i} w

having

u_{i}

and

T_{2}

and

T_{3}

are subtrees of

K - u_{i} u_{i + 1} - u_{i} w

having

u_{i + 1}

and w, respectively.

Let

T^{*} = K - {w w_{1}, w w_{2}, \dots, w w_{q}} + {u_{s} w_{1}, u_{s} w_{2}, \dots, u_{s} w_{q}}

. Clearly,

T^{*}

has t pendant vertices and

$e c_{K} (u) < e c_{T^{*}} (u)$ and $d_{K} (u) = d_{T^{*}} (u)$ for all $u \in (T_{1} \cup (T_{3} - w))$ ,
$e c_{K} (w) < e c_{T^{*}} (w), d_{K} (w) = q + 1, d_{T^{*}} (w) = 1$ ,
$e c_{K} (u) \leq e c_{T^{*}} (u)$ and $d_{K} (u) = d_{T^{*}} (u)$ for all $u \in (T_{2} - u_{s})$ ,
$e c_{K} (u_{s}) = e c_{T^{*}} (u_{s}), d_{K} (u_{s}) = 1, d_{T^{*}} (u_{s}) = q + 1$ .

From the above, we have

\begin{matrix} ξ_{α}^{e c} (T^{*}) - ξ_{α}^{e c} (K) & > d_{T^{*}} (w) e c_{T^{*}} {(w)}^{α} + d_{T^{*}} (u_{s}) e c_{T^{*}} {(u_{s})}^{α} - d_{K} (w) e c_{K} {(w)}^{α} - \\ d_{K} (u_{s}) e c_{K} {(u_{s})}^{α} \\ = & e c_{T^{*}} {(w)}^{α} + (q + 1) e c_{T^{*}} {(u_{s})}^{α} - (q + 1) e c_{K} {(w)}^{α} - e c_{K} {(u_{s})}^{α} \\ < & q (e c_{T^{*}} {(u_{s})}^{α} - e c_{K} {(w)}^{α}) \leq 0 \end{matrix}

the second last inequality is due to

e c_{K} (w) < e c_{T^{*}} (w)

while the last inequality is due to

e c_{T^{*}} {(u_{s})}^{α} - e c_{K} {(w)}^{α} \leq 0

, and the result gives a contradiction that K has the minimum GECI for

α < 0

Suppose that

j \in {⌈ \frac{t + 1}{2} ⌉, \dots, s - 2}

be a largest integer such that there is a vertex x adjacent with

u_{j}

and

u_{j - 1} \neq x \neq u_{j + 1}

. Let

N_{K} (x) = {u_{j}, w_{1}^{'}, w_{2}^{'}, \dots, w_{p}^{'}}

, where

p \geq 2

. Similar to the above discussion we can construct a new tree by removing

w_{k}^{'} s

from x and joining these to

u_{0}

, and the new graph has less GECI for

α < 0

, which leads to a contradiction. Hence, K is a caterpillar. □

Claim 2.

K is an element of

⊤_{r}^{t}

Proof of Claim 2:

From the above claim, we conclude that K has the diameter

r - t + 1

. Let

P_{r - t + 2} = u_{0} u_{1} \dots u_{r - t + 1}

be the longest path of K. Suppose that

i \in {2, 3, \dots, ⌈ \frac{t + 1}{2} ⌉}

be the smallest integer such that

d (u_{i}) > 0

and

N_{K} (u_{i}) = {u_{i - 1}, u_{i + 1}, w_{1}, \dots, w_{q}}

. Now, we construct a new graph

T^{* *} = K - {u_{i} w_{1}, u_{i} w_{2}, \dots, u_{i} w_{q}} + {u_{1} w_{1}, u_{1} w_{2}, \dots, u_{1} w_{q}}

Clearly,

e c_{K} (w_{i}) < e c_{T^{* *}} (w_{i})

for every

w_{i}

’s and for other vertices

e c_{K} (x) = e c_{T^{* *}} (x)

. Moreover,

d_{T^{* *}} (v_{i}) = d_{K} (v_{i}) - s

d_{T^{* *}} (v_{1}) = d_{K} (v_{1}) + s

and for any other vertices we have

d_{T^{* *}} (x) = d_{K} (x)

. This implies that

\begin{matrix} ξ_{α}^{e c} (K) - ξ_{α}^{e c} (T^{* *}) & > d_{k} (u_{1}) e c_{K} {(u_{1})}^{α} + d (u_{i}) e c_{K} {(u_{i})}^{α} - d_{T^{* *}} (u_{1}) e c_{T^{* *}} {(u_{1})}^{α} - \\ d_{T^{* *}} (u_{i}) e c_{T^{* *}} {(u_{i})}^{α} \\ = q (- e c_{K} {(u_{1})}^{α} + e c_{K} {(u_{i})}^{α}) > 0 \end{matrix}

the last inequality is due to

e c_{K} (u_{i}) < e c_{K} (u_{1})

and

α < 0

. This gives a contradiction that K has the minimum generalized GECI.

Now, assume that

i \in {⌈ \frac{t + 1}{2} ⌉, \dots, r - t - 1}

is the largest integer such that

d (v_{i}) > 2

and

N_{K} (u_{i}) = {u_{i - 1}, u_{i + 1}, w_{1}^{'} \dots, w_{q}^{'}}

. We construct a new graph

T^{* * *} = K - u_{i} w_{1}^{'} - u_{i} w_{2}^{'} - \dots - u_{i} w_{q}^{'} + u_{n - t} w_{1}^{'} + u - r - t w_{2}^{'} + \dots + u - r - t w_{q}^{'}

. Similarly, as above, we obtain

ξ_{α}^{e c} (K) - ξ_{α}^{e c} (T^{* * *})

> 0

and we have again a contradiction. Hence, we have

K \in ⊤_{r}^{t}

. □

Let

R_{1}

and

R_{2}

be two non-trivial graphs having

u \in V (R_{1})

and

v \in V (R_{2})

. The graphs

R^{*}

and

R^{* *}

are obtained from

R_{1} \cup R_{2}

by adding an edge

u v

and by identifying u and v to a new vertex say u and adding a pendant edge

u v

, respectively.

Lemma 2.

Let

R^{*}

and

R^{* *}

be two above defined graphs, then for

α < 0

, we have

ξ_{α}^{e c} (R^{*}) < ξ_{α}^{e c} (R^{* *})

Proof.

Clearly, for any

w \in R_{1} \cup R_{2} - {u, v}

, we have

e c_{R^{*}} (w) \geq e c_{R^{* *}} (w)

and

d_{R^{*}} (w) = d_{R^{* *}} (w)

. For vertices u and v, we have

$e c_{R^{*}} (u) = m a x {e c_{H_{1} (u)}, e c_{H_{2}} (v) + 1}, d_{R^{*}} (u) = d_{H_{1}} (u) + 1$ ,M
$e c_{R^{*} *} (u) = m a x {e c_{H_{1} (u)}, e c_{H_{2}} (v)}, d_{R^{* *}} (u) = d_{H_{1}} (u) + d_{H_{2}} (v) + 1,$
$e c_{R^{*}} (v) = m a x {e c_{H_{1} (u)} + 1, e c_{H_{2}} (v)}, d_{R^{*}} (v) = d_{H_{2}} (v) + 1,$
$e c_{R^{*} *} (v) = m a x {e c_{H_{1} (u)} + 1, e c_{H_{2}} (v) + 1}, d_{G^{*}} (v) = 1 .$

Now, we have the following cases:

Case 1.

e c_{H_{1}} (u) \geq e c_{H_{2}} (v)

Here, we have

e c_{R^{*}} (u) = e c_{H_{1}} (u), e c_{R^{* *}} (u) = e c_{H_{1}} (u), e c_{R^{*}} (v) = e c_{H_{1}} (u) + 1,

and

e c_{R^{* *}} (v) = e c_{H_{1}} (u) + 1

. This gives

\begin{matrix} ξ_{α}^{e c} (R^{*}) - ξ_{α}^{e c} (R^{* *}) & \leq d_{R^{*}} (u) e c_{H_{1}} {(u)}^{α} - d_{R^{* *}} (u) e c_{H_{1}} {(u)}^{α} + d_{R^{*}} (v) {(e c_{H_{1}} (u) + 1)}^{α} \\ - d_{R^{* *}} (v) {(e c_{H_{1}} (u) + 1)}^{α} \\ = d_{H_{2}} (v) ({(e c_{H_{1}} + 1)}^{α} - e c_{H_{1}} {(u)}^{α}) < 0 \end{matrix}

α < 0

Case 2.

e c_{H_{1}} (u) \leq e c_{H_{2}} (v)

First consider

e c_{H_{1}} (u) = e c_{H_{2}} (v)

. Here, we have

e c_{R^{*}} (u) = e c_{H_{1}} (u) + 1, e c_{R^{*} *} (u) = e c_{H_{1}} (u), e c_{R^{*}} (v) = e c_{H_{1}} + 1, e c_{R^{* *}} (v) = e c_{H_{1}} (u) + 1

This implies that

\begin{matrix} ξ_{α}^{e c} (R^{*}) - ξ_{α}^{e c} (R^{* *}) & \leq (d_{H_{1}} (u) + 1) {(e c_{H_{1}} (u) + 1)}^{α} - (d_{H_{1}} (u) + d_{H_{2}} (v) + 1) {(e c_{H_{1}} (u) + 1)}^{α} \\ + (d_{H_{2}} (v) + 1) {(e c_{H_{1}} (u) + 1)}^{α} - {(e c_{H_{1}} (u) + 1)}^{α} \\ = (d_{H_{1}} (u) + d_{H_{2}} (v) + 1) ({(e c_{H_{1}} (u) + 1)}^{α} - e c_{H_{1}} {(u)}^{α}) < 0, \end{matrix}

Now, take

e c_{H_{1}} (u) < e c_{H_{2}} (v)

, then we have

e c_{R^{*}} (u) = e c_{H_{2}} (v) + 1, e c_{R^{* *}} (u) = e c_{H_{2}} (v), e c_{R^{*}} (v) = e c_{H_{2}} (v), e c_{R^{* *}} (v) = e c_{H_{2}} (v) + 1

. This implies that

\begin{matrix} ξ_{α}^{e c} (R^{*}) - ξ_{α}^{e c} (R^{* *}) & \leq (d_{H_{1}} (u) + 1) {(e c_{H_{2}} (v) + 1)}^{α} - (d_{H_{1}} (u) + d_{H_{2}} (v) + 1) {(e c_{H_{2}} (v))}^{α} \\ + (d_{H_{2}} (v) + 1) {(e c_{H_{2}} (v))}^{α} - {(e c_{H_{2}} (v) + 1)}^{α} \\ = (d_{H_{1}} (u)) ({(e c_{H_{2}} (v) + 1)}^{α} - e c_{H_{2}} {(v)}^{α}) < 0, \end{matrix}

□

Theorem 8.

Let R be a graph of order n with

t \geq 1

cut edges, then for

α < 0

, we have

ξ_{α}^{e c} (R) \leq 2^{α} ({(r - t - 1)}^{2} + t) + r - 1

and the equality holds if and only if

R = K_{r}^{t}

Proof.

Let R be the graph with the maximum general eccentric connectivity index, then by Lemma 2, all the cut edges are pendant edges in R. Now, the problem is to find the maximum GECI with given pendant edges, which is discussed in Theorem 7, hence the result. □

Let

C_{r, t}

be a cactus by adding t independent edges among pendant vertices of

S_{r}

Theorem 9.

Let R be a cactus of order greater than four having t cycles. Then, for

α < 0

, we have

ξ_{α}^{e c} (R) \leq n (2^{α} + 1) + 2^{α + 1} t - (1 + 2^{α})

and the equality holds if and only if

R = C_{r, t}

Proof.

Let

V_{1}

and

V_{2}

be the set of vertices of eccentricity one and greater than one, respectively. Clearly,

| V_{1} | \leq 1

. Otherwise assume that u and v are vertices of eccentricity one and these vertices must have degree

r - 1

. Then, there exist cycles having common edges in

R L,

, which implies that R is not a cactus. Now, we have the following two cases:

Case 1. When

| V_{1} | = 1

Let u be the vertex of eccentricity one, this implies that each vertex of R is adjacent to u. Hence, the cactus R is obtained by adding t independent edges among pendant vertices of

S_{r}

, in other words,

R = C_{r, t}

Case 2. When

| V_{1} | = 0

Here, every vertex of G has eccentricity greater than one and there are exactly

r + t - 1

edges in R. Then,

ξ_{α}^{e c} (R) \leq 2^{α} \sum_{u \in V (R)} d (u) = 2^{α + 1} (r + t - 1)

. This implies that

ξ_{α}^{e c} (R) - ξ_{α}^{e c} (C_{r, t}) \leq 2^{α + 1} (n + t - 1) - n (2^{α} + 1) - 2^{α + 1} t + (1 + 2^{α}) = (r - 1) (2^{α + 1} - 2^{α} - 1) < 0

, since

α < 0

which is required proof. □

The following corollaries are direct consequences of the above result.

Corollary 4.

Let R be a tree of order n, then for

α < 0

, we have

ξ_{α}^{e c} (R) \leq (r - 1) (2^{α} + 1)

and the equality holds if and only

R = S_{r}

Corollary 5.

Let R be a unicyclic graph of order r, then for

α < 0

, we have

ξ_{α}^{e c} (R) \leq r (2^{α} + 1) + 2^{α + 1} - 2^{α} - 1

and the equality holds if and only

R = C_{r, 1}

3. Conclusions

The general eccentric connectivity index is a newly introduced topological index. The study of this newly introduced topological index is a useful and interesting task. We put some lower and upper bounds on this topological index by using some graph parameters. It will be interesting to find the extremal graphs for other classes of graphs by using some graph parameters such as the number of vertices with the given parameter, the number of vertices with the given maximum degree, etc.

Author Contributions

Conceptualization, M.I., A.J., X.Y., X.Z. and M.K.J.; methodology, M.I., A.J., X.Y., X.Z. and M.K.J.; software, M.I., A.J., X.Y., X.Z. and M.K.J.; validation, M.I., A.J., X.Y., X.Z. and M.K.J.; formal analysis, M.I., A.J., X.Y., X.Z. and M.K.J.; investigation, M.I., A.J., X.Y., X.Z. and M.K.J.; resources, M.I., A.J., X.Y., X.Z. and M.K.J.; data curation, M.I., A.J., X.Y., X.Z. and M.K.J.; writing—original draft preparation, M.I., A.J., X.Y., X.Z. and M.K.J.; writing—review and editing, M.I., A.J., X.Y., X.Z. and M.K.J.; visualization, M.I., A.J., X.Y., X.Z. and M.K.J.; supervision, M.I., A.J., X.Y., X.Z. and M.K.J.; project administration, M.I.; funding acquisition, M.K.J., X.Y., X.Z. and M.I. All authors have read and agreed to the published version of the manuscript.

Funding

This research project is supported by the Natural Science Foundation of Anhui Province Higher School (KJ2020A0780, KJ2020A0779).

Data Availability Statement

The data used to support the findings of the results are included within the article.

Conflicts of Interest

The authors declare that there is no conflict of interests.

References

Bondy, J.A.; Murty, U.S.R. Graph Theory; Springer: London, UK, 2008. [Google Scholar]
Sharma, V.; Goswami, R.; Madan, A.K. Eccentric connectivity index: A novel highly discriminating topological descriptor for structure-property and structure-activity studies. J. Chem. Int. Model 1997, 37, 273–282. [Google Scholar]
Zhou, B.; Du, Z. On eccentric connectivity index. Math. Commun. Math. Comput. Chem. 2010, 63, 181–198. [Google Scholar]
Morgan, M.J.; Mukwembi, S.; Swart, H.C. On the eccentric connectivity index of a graph. Discrete Math. 2011, 311, 1229–1234. [Google Scholar] [CrossRef] [Green Version]
Morgan, M.J.; Mukwembi, S.; Swart, H.C. A lower bound on the eccentric connectivity index of a graph. Discrete Appl. Math. 2012, 160, 248–258. [Google Scholar] [CrossRef] [Green Version]
Liu, J.B.; Shaker, H.; Nadeem, I.; Farahani, M.R. Eccentric connectivity index of t-polyacenic nanotubes. Adv. Mat. Sci. Eng. 2019, 9062535. [Google Scholar] [CrossRef] [Green Version]
Wu, Y.; Chen, Y. On the extremal eccentric connectivity index of graphs. Appl. Math. Comput. 2018, 331, 61–68. [Google Scholar] [CrossRef]
Gupta, S.; Singh, M.; Madan, A.K. Application of graph theory: Relationship of eccentric connectivity index and Wiener’s index with anti-inflammatory activity. J. Math. Anal. Appl. 2002, 266, 259–268. [Google Scholar] [CrossRef] [Green Version]
Ilić, A. Eccentric connectivity index. arXiv 2011, arXiv:1103.2515. [Google Scholar]
Došlic, T.; Saheli, M. Eccentric connectivity index of composite graphs. Util. Math. 2014, 95, 3–22. [Google Scholar]
Doslic, T.; Saheli, M.; Vukicevic, D. Eccentric connectivity index: Extremal graphs and values. Iran. J. Math. Chem. 2010, 1, 45–56. [Google Scholar]
Hua, H.; Das, K.C. The relationship between the eccentric connectivity index and Zagreb indices. Discrete Appl. Math. 2013, 161, 2480–2491. [Google Scholar] [CrossRef]
Das, K.C.; Trinajstić, N. Relationship between the eccentric connectivity index and Zagreb indices. Comput. Math. Appl. 2011, 4, 1758–1764. [Google Scholar] [CrossRef] [Green Version]
Dankelmann, P.; Morgan, M.J.; Mukwembi, S.; Swart, H.C. On the eccentric connectivity index and Wiener index of a graph. Quaest. Math. 2014, 37, 39–47. [Google Scholar] [CrossRef]
Nacaroğlu, Y.; Maden, A.D. On the eccentric connectivity index of unicyclic graphs. Iran. J. Math. Chem. 2018, 9, 47–56. [Google Scholar]
Rather, B.A.; Ali, F.; Alsaeed, S.; Naeem, M. Hosoya Polynomials of Power Graphs of Certain Finite Groups. Molecules 2022, 27, 6081. [Google Scholar] [CrossRef]
Rather, B.A.; Aouchiche, M.; Imran, M.; Pirzada, S. On arithmetic–Geometric eigenvalues of graphs. Main Group Metal Chem. 2022, 45, 111–123. [Google Scholar] [CrossRef]
Rather, B.A.; Imran, M. Sharp bounds on the Sombor energy of graphs. MATCH Comm. Math. Comp. Chem. 2022, 88, 605–624. [Google Scholar] [CrossRef]
De, N. Relationship between augmented eccentric connectivity index and some other graph invariants. Int. J. Adv. Math. Sci. 2013, 1, 26–32. [Google Scholar] [CrossRef] [Green Version]
Alishahi, M.; Shalmaee, S.H. On the edge eccentric and modified edge eccentric connectivity indices of linear benzenoid chains and double hexagonal chains. J. Mol. Struct. 2020, 1204, 127446. [Google Scholar] [CrossRef]
Ilić, A.; Yu, G.; Feng, L. On the eccentric distance sum of graphs. J. Math. Anal. Appl. 2011, 381, 590–600. [Google Scholar] [CrossRef]
Vertik, T.; Masre, M. General eccentric connectivity index of trees and unicyclic graphs. Discrete Appl. Math. 2020, 284, 301–315. [Google Scholar]

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Yu, X.; Imran, M.; Javed, A.; Jamil, M.K.; Zuo, X. Bounds on the General Eccentric Connectivity Index. Symmetry 2022, 14, 2560. https://doi.org/10.3390/sym14122560

AMA Style

Yu X, Imran M, Javed A, Jamil MK, Zuo X. Bounds on the General Eccentric Connectivity Index. Symmetry. 2022; 14(12):2560. https://doi.org/10.3390/sym14122560

Chicago/Turabian Style

Yu, Xinhong, Muhammad Imran, Aisha Javed, Muhammad Kamran Jamil, and Xuewu Zuo. 2022. "Bounds on the General Eccentric Connectivity Index" Symmetry 14, no. 12: 2560. https://doi.org/10.3390/sym14122560

APA Style

Yu, X., Imran, M., Javed, A., Jamil, M. K., & Zuo, X. (2022). Bounds on the General Eccentric Connectivity Index. Symmetry, 14(12), 2560. https://doi.org/10.3390/sym14122560

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Bounds on the General Eccentric Connectivity Index

Abstract

1. Introduction

2. Main Results

3. Conclusions

Author Contributions

Funding

Data Availability Statement

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI