Exploring the SDE index: a novel approach using eccentricity in graph analysis

Abstract

In this article, we present an enhanced version of the symmetric division deg index (sdd-index) known as symmetric division eccentric index or SDE index, for short. Unlike its predecessor, SDE employs eccentricity instead of vertex degree to assess the properties of a graph G. In this paper, we first give some bounds for SDE index of a connected graph G with fixed size m. For two connected graphs ${\varvec{G}}_{\varvec{1}}$ and ${\varvec{G}}_{\varvec{2}}$ of order ${\varvec{n}}_{\varvec{1}}$ and ${\varvec{n}}_{\varvec{2}}$, employing these bounds, we compute the SDE index for two classes of graph products, e.g., the Cartesian product and Corona product. As an application, we determine the structure of graphs with two non-equi-centric edges. Our theorems generalize the recent results for the extended adjacency index of a graph. Besides, this research significantly contributes to the comprehension of graph analysis techniques and offers valuable insights into the relationship between SDE and various graph properties.

1 Introduction

Graph theory, a fundamental area of mathematics, plays a pivotal role in modelling real-world networks and understanding their intricate structures. In this paper, we present an advanced variant of the symmetric division degree index (SDD-index) called as symmetric division eccentric index (or shortly SDE index) which leverages eccentricity instead of vertex degree for evaluating graph properties.

The SDD-index has been widely used to measure the distribution of edges in a graph. However, by incorporating eccentricity, the SDE index offers a refined perspective on graph analysis. Eccentricity captures the notion of how far a vertex is from other vertices in terms of shortest path lengths, providing a more comprehensive evaluation of graph structure.

The primary objective of this study is to explore new bounds and new properties of the SDE index as well as investigate its relationship with other prominent graph indices. Specifically, we will examine the graph invariants such as the first and second Zagreb indices, harmonic index, atom-bond-connectivity index, Randic index, the size of the graph automorphism group, and the sum connectivity index. By calculating these indices and analyzing their correlations with SDE, we aim to gain a deeper understanding of the interplay between different graph measures and the enhanced SDE index.

Understanding such relationships can lead to valuable applications in various fields, including network analysis, network modelling, and biological network characterization. Moreover, uncovering the connections between the SDE index and established graph indices may offer new insights into graph properties that were previously unexplored.

In the subsequent sections of this paper, we will introduce the methodology behind the calculation of the SDE index and graph indices. We will then present our findings on the correlation between SDE and other indices, highlighting any significant patterns or observations. Finally, we will discuss the implications of our results and potential avenues for future research.

In conclusion, by introducing the SDE index and investigating its relationships with various graph indices, this paper contributes to the advancement of graph theory and provides a deeper understanding of graph properties.

2 Preliminary results

We denote a graph by $G = (V, E)$, where V(G) represents the set of vertices and E(G) represents the set of edges. In this paper, all graphs are assumed to be simple, connected, and undirected.

The Cartesian product of two graphs, G and H, denoted as $G_{1} \times G_{2}$, results in a new graph with the vertex set $V(G) \times V(H)$. Two vertices $(g_1, h_1)$ and $(g_2, h_2)$ are adjacent if and only if either $g_1 = g_2$ and $h_1h_2 \in E(H)$, or if $h_1 = h_2$ and $g_1g_2 \in E(G)$. To obtain further information on other terms related to graph theory, refer to [14]. The corona product of two graphs $G_1$ and $G_2$, represented as $G_1 \circ G_2$, is obtained by taking |$V(G_1)$| copies of $G_2$ and connecting each vertex of the i-th copy with the corresponding vertex $v_i \in V(G_1)$, see for example [5]. It follows that the number of vertices in $G_1 \circ G_2$, denoted by |$V(G_1 \circ G_2)$|, is given by |$V(G_1)$| (1+|$V(G_2)$|), and the number of edges, denoted by |$E(G_1 \circ G_2)$|, is calculated as |$E(G_1)$| + |$V(G_1)$|(|$(V(G_2)$|+|$E(G_2)$|), see [8].

The distance between two vertices $u,v \in V$, denoted as d(u, v), is defined as the length of the shortest path between vertices u and v in graph G. The eccentricity of a vertex v, denoted as $\varepsilon (v)$, is the maximum distance from v to any other vertex in G:

$$\begin{aligned} \varepsilon (v)= max(d(u, v));\hbox { for all }u\in V(G). \end{aligned}$$

The radius of a graph G, denoted as r(G), is the minimum eccentricity among all vertices:

$$\begin{aligned} r(G) = min(\varepsilon (v));\hbox { for all }v\in V(G). \end{aligned}$$

The diameter of a graph G, denoted as d(G), is the maximum eccentricity among all vertices [1]:

$$\begin{aligned} d(G) = max(\varepsilon (v));\hbox { for all }v\in V(G). \end{aligned}$$

A vertex v of G is called a central vertex if $\varepsilon (v)=r(G)$ and center C(G) of G is the collection of all such vertices in G. A graph is referred to as a self-centered graph if $r(G)=d(G)$. In other words, in a self-centered graph, the eccentricity is the same for all vertices in the graph. This can be equivalently stated as the radius and diameter of the graph, which represent the smallest and largest eccentricities, respectively, being equal. Within this piece, we introduce the notion of an "equi-centric" edge (or ec-edge for short) in a graph, which refers to an edge, where both ends have equal eccentricity. By defining and identifying equi-centric edges, we can gain deeper insights into the structural properties of graphs. By an equi-centric edge, we mean an edge that endpoints have the same eccentricity. An edge which is not equi-centric is called a non-equi-centric edge (or nec-edge for short). This means that for such an edge, the maximum distance from each endpoint to any other vertex in the graph is identical.

A graph G is called as nec-graph if G has no ec-edge. Equi-centric edges play a significant role in understanding and analyzing various graph structures. Identifying equi-centric edges can be valuable in several applications. For example, in social network analysis, detecting equi-centric edges may provide insights into individuals who exhibit similar influence or centrality within a network. Additionally, in transportation networks, identifying equi-centric edges could highlight roads or paths, where travel time remains constant regardless of the starting or ending point. Studying equi-centric edges contributes to the broader understanding of graph properties and helps uncover hidden patterns or connections within complex networks. By exploring the characteristics and implications of equi-centric edges, researchers and practitioners can enhance their analyses and make informed decisions in a wide range of fields.

A pendant edge in a graph refers to an edge that is incident to only one vertex. In other words, one end of the edge connects to a vertex while the other end remains unconnected. A cut edge, also known as a bridge, is an edge in a graph whose removal increases the number of connected components in the graph. In other words, if we remove a cut edge from a graph, the graph becomes disconnected or split into two or more separate parts.

The edge connectivity number of a graph is the minimum number of edges that must be removed in order to disconnect the graph. It represents the minimum number of edges that need to be remove in order to separate the graph into multiple disconnected components.

A leaf node, also known as a leaf vertex or terminal vertex, refers to a node in a graph that has only one edge connected to it. Here we denote leaf nodes by LF.

Graph indices are numerical quantities associated with graphs that provide insights into their structural properties and can be used to analyze various aspects of graph behavior. In this paper, we focus on several important graph indices: the graph independence number, first and second Zagreb index, harmonic index, ABC index, Randic index, size of the graph automorphism group, and sum connectivity index.

The graph independence number, denoted as $\alpha (G)$, is the maximum cardinality of an independent set in a graph G. An independent set is a subset of vertices in which no two vertices are adjacent.

One of the most graph indices is the widely recognized Zagreb index presented in [9]. When considering a (molecular) graph G, the first Zagreb index $M_1(G)$ and the second Zagreb index $M_2(G)$ can be defined as follows:

$$\begin{aligned} M_1(G)&= \sum _{v\in V(G)} d_G(v)^2, \\ M_2(G)&= \sum _{uv\in E(G)} d_G(u)d_G(v), \end{aligned}$$

where $d_G(v)$ denotes the degree of vertex v in graph G.

The harmonic index, represented as H(G), is a graph property initially presented in reference [4]. It is computed for a given graph G using the following formula:

$$\begin{aligned}H(G)=\sum _{uv\in E(G)}\frac{2}{d_G(u) + d_G(v)}. \end{aligned}$$

The atom-bond-connectivity index (or shorting the ABC index) is determined by the following formula [3]:

$$\begin{aligned}ABC(G)=\sum _{uv\in E(G)}\sqrt{\frac{d_G(u) +d_G(v) -2}{d_G(u) d_G(v) }}. \end{aligned}$$

The Randic index, denoted as R(G), is a molecular descriptor originally developed for chemical compounds but applicable to graphs as well. It is defined as the sum of the reciprocal square roots of the degrees of all vertices in a graph G. The R(G) captures the complexity and branching patterns of a graph and is defined as [12]

$$\begin{aligned}R(G)=\sum _{uv\in E(G)}\frac{1}{\sqrt{d_G(u)d_G(v)} }. \end{aligned}$$

The size of the automorphism group, denoted as |Aut(G)|, represents the number of automorphisms of a graph G. An automorphism is an isomorphism from a graph to itself, preserving both the vertex set and the edge set. The size of the graph automorphism group reflects the symmetry and structural regularity of a graph.

The sum connectivity index, denoted as SC(G) is defined as [16]

$$\begin{aligned}SC(G)=\sum _{uv\in E(G)}\frac{1}{\sqrt{d_G(u)+d_G(v)} }. \end{aligned}$$

The symmetric division degree index (SDD-index) was defined by Vukičević [13] as follows:

$$\begin{aligned} SDD(G)&= \sum _{uv\in E(G)}\left[ \frac{d_G(u)}{d_G(v)} + \frac{d_G(v)}{d_G(u)}\right] . \end{aligned}$$

In this way, we define the SDE index based on eccentricities of vertices as follows:

$$\begin{aligned} SDE(G)&= \sum _{uv\in E(G)}\left[ \frac{\varepsilon (u)}{\varepsilon (v)} + \frac{\varepsilon (v)}{\varepsilon (u)}\right] . \end{aligned}$$

In graph theory, a theta graph (denoted as $\Theta$-graph) is a specific type of connected graph that consists of three internally disjoint paths, each with a length of at least one edge, connecting two vertices (u and v) with lengths k, l, and m, where k, l, and m are non-negative integers. The three paths are mutually disjoint, meaning they do not share any vertices or edges except for the endpoints u and v.

Several studies have been conducted to explore the relationship between network properties and graph parameters. Ghorbani et al. [7] focused on investigating various topological indices such as the first Zagreb index, second Zagreb index, spectral radius, Randic index, Laplacian Estrada index, Laplacian Energy, Harary index, Estrada index, energy, Balaban index and atom-bond connectivity across different networks. Additionally, the authors in [6] examined networks of fullerene molecules. In this paper, our objective is to explore the correlation between graph indices and the generalized symmetric division degree index SDE in protein networks. Our focus will be on investigating and analyzing how changes in graph indicators impact the SDE. This research aims to enhance our understanding of network behavior and the factors influencing it.

Example 2.1

Here, we determine the SDE index of a star graph on n vertices. Since surrounded vertices have an eccentricity of two and the eccentricity of the central vertex is one, we obtain

$$\begin{aligned} SDE(S_{n})&= \sum _{uv\in E(S_{n})}\left[ \frac{\varepsilon (u)}{\varepsilon (v)} + \frac{\varepsilon (v)}{\varepsilon (u)}\right] \\&= \sum _{uv\in E(S_{n})}\left[ \frac{1}{2} + \frac{2}{1}\right] \\&= \frac{5}{2} (n-1). \end{aligned}$$

The star graph is a special case of an edge-transitive graph. In general, we have the following theorem.

Theorem 2.1

Let G be a graph with size m. Then

i):

$2m\le SDE(G)\le \frac{5}{2}m$,

ii):

If G is an edge-transitive graph, then $SDE(G)=2m$ or $SDE(G)=m(\frac{r}{d}+\frac{d}{r})$, where r and d are the radius and diameter of the graph, respectively.

Proof

First, we show that for an edge $e=uv$, $\varepsilon (u)=\varepsilon (v)$ or $\varepsilon (u)=\varepsilon (v)+1$. Suppose $\varepsilon (u)\ne \varepsilon (v)$, there exists a path P of length $\varepsilon (u)$ between u and a vertex such as $u_n$ that is $P=u,u_{1}, u_{2}, u_{3} \ldots u_{n}$. Clearly, if $v\notin \left\{ u, u_{1}, u_{2},\ldots , u_{n} \right\}$ then $\varepsilon (v)>\varepsilon (u)$ which is a contradiction. Since u and v are adjacent, without loss of generality, we can assume that $u_1=v$ and we are done.

i) Given that for each edge $e=uv$, since $|\varepsilon (u)-\varepsilon (v)|\le 1$, we have following two cases:

• If $\varepsilon (u)=\varepsilon (v)$, then $\frac{\varepsilon (u)}{\varepsilon (v)}+\frac{\varepsilon (v)}{\varepsilon (u)}=2$,

• If $\varepsilon (u)\ne \varepsilon (v)$, then $\frac{\varepsilon (u)}{\varepsilon (v)}+\frac{\varepsilon (v)}{\varepsilon (u)}\le \frac{5}{2}$.

This completes the proof of the first claim.

ii) Assume that G is edge-transitive. If G is vertex-transitive, then G is self-centered and so $SDE(G)=2m$. If G is edge-transitive but not vertex-transitive, since the action of Aut(G) on the edges is transitive, for each edge $e=uv$ and an arbitrary vertex w, we have $\varepsilon (w)\in \left\{ r, d\right\}$ and by discussion before the proof of Part i) the proof is complete. $\square$

Example 2.2

Now consider the path graph $P_n$ with vertices $v_1, v_2,\ldots ,v_n$. It is easy to see that $\varepsilon (v_1)=\varepsilon (v_n)$, $\varepsilon (v_2)=\varepsilon (v_{n-1})$, etc. This leads us to conclude that if n is even, then we have

$$\begin{aligned} SDE(P_n)&= \sum _{uv\in E(P_n)} \left[ \dfrac{\varepsilon \left( u\right) }{\varepsilon \left( v\right) } + \dfrac{\varepsilon \left( v\right) }{\varepsilon \left( u\right) }\right] \\&= 2 \times \left[ \dfrac{n-1}{n-2} + \dfrac{n-2}{n-1} + \dfrac{n-2}{n-3} + \dots + \dfrac{n-\dfrac{n-2}{2}}{n-\dfrac{n}{2}} + \dfrac{n-\dfrac{n}{2}}{n-\dfrac{n-2}{2}}\right] \\&\quad + \left[ \dfrac{n-\dfrac{n}{2}}{n-\dfrac{n}{2}} + \dfrac{n-\dfrac{n}{2}}{n-\dfrac{n}{2}}\right] . \end{aligned}$$

And if n is odd, we obtain

$$\begin{aligned} SDE(P_{n})&= \sum _{uv\in E(P_{n})}\left[ \frac{\varepsilon (u)}{\varepsilon (v)} + \frac{\varepsilon (v)}{\varepsilon (u)}\right] \\&= 2 \times \left[ \left( \frac{n-1}{n-2} + \frac{n-2}{n-1}\right) + \left( \frac{n-2}{n-3} + \frac{n-3}{n-2}\right) + \cdots \right. \\&\quad + \left. \left( \frac{n-\frac{n+1}{2}}{n-\frac{n-1}{2}} + \frac{n-\frac{n-1}{2}}{n-\frac{n+1}{2}}\right) \right] . \end{aligned}$$

Example 2.3

It is well-known that for a tree T, the center C(T) is isomorphic to $K_1$ or $K_2$. The star graph $S_n$ is an example for which $C(S_n)\cong K_1$ and for the bistar tree $S_{m,n}$, we have $C(S_{m,n})\cong K_2$. This leads us to conclude

$$\begin{aligned} SDE(S_{m,n})&= \sum _{uv\in E(S_{m,n})}\left[ \frac{\varepsilon (u)}{\varepsilon (v)} + \frac{\varepsilon (v)}{\varepsilon (u)}\right] \\&= (\frac{2}{2} + \frac{2}{2}) + m \times (\frac{2}{3} + \frac{3}{2}) + n \times (\frac{2}{3} + \frac{3}{2}) \\&= \frac{13}{6}(m+n) + 2. \end{aligned}$$

3 Results

This section begins with the establishment of bounds for the SDE index in a graph, providing valuable information about its potential range. The aim of this section is to obtain bounds for SDE index. Besides, we characterize graphs with no or with two ec-edges.

Theorem 3.1

Consider two graphs $G_1$ and $G_2$ of respectively orders $n_1$ and $n_2$ with sizes $m_1$ and $m_2$. Then

• 1. If both $G_1$ and $G_2$ are self-centered, then

  $$\begin{aligned} SDE(G_{1} \times G_{2} ) =2 n_{1} m_2 + 2n_{2} m_1. \end{aligned}$$

• 2. If one of the graphs $G_1$ or $G_2$ is not self-centered, then

  $$\begin{aligned} SDE(G_{1} \times G_{2} ) < \frac{13}{6}n_1m_2+2n_2m_1. \end{aligned}$$

  Equality holds if and only if $G_1 \cong S_{n_1}$ and $G_2 \cong K_{n_2}$.

Proof

By definition of the Cartesian product of two graphs, we have:

$$\begin{aligned} {|} E (G_1 \mathrm {\times } G_2){|} = {|} E (G_1){|}. {|} V (G_2){|} + {|} E (G_2){|}. {|} V (G_1){|}, \end{aligned}$$

and

$$\begin{aligned}{\varepsilon }_{G_{\textrm{1}}\times G_{\textrm{2}}}\mathrm {(}u_i,v_j\mathrm {)=}{\varepsilon }_{G_{\textrm{1}}}\mathrm {(}u_i\mathrm {)}+{\varepsilon }_{G_{\textrm{2}}}\mathrm {(}v_j\mathrm {)}.\end{aligned}$$

• 1. If both $G_1$ and $G_2$ are self-centered, then $G_1\times G_2$ is self-centered and we are done.

• 2. Suppose $X=G_{1}\times G_{2}$. Without loss of generality, suppose that $G_2$ is not self-centered, then

  $$\begin{aligned} SDE(X)&= \sum _{ {[(u_{i} ,v_{j} ),(u_{k} ,v_{l} )]\in E(X)} {(u_{i} ,v_{j} )\ne (u_{k} ,v_{l} )}}{\left[ \frac{\varepsilon _{X}(u_i,v_j)}{\varepsilon _{X}(u_k,v_l)} + \frac{\varepsilon _{X}(u_k,v_l)}{\varepsilon _{X}(u_i,v_j)}\right] } \\&= \sum _{ {[(u_i,v_j),(u_i,v_l)]\in E(X)} {v_jv_l\in E(G_{2})}} {\left[ \frac{\varepsilon _{X}(u_i,v_j)}{\varepsilon _{X}(u_i,v_l)} + \frac{\varepsilon _{X}(u_i,v_l)}{\varepsilon _{X}(u_i,v_j)}\right] } \\&\quad + \sum _{ {[(u_i,v_j),(u_k,v_j)]\in E(X)} {u_iu_k\in E(G_{1})}} {\left[ \frac{\varepsilon _{X}(u_i,v_j)}{\varepsilon _{X}(u_k,v_j)} + \frac{\varepsilon _{X}(u_k,v_j)}{\varepsilon _{X}(u_i,v_j)}\right] }. \end{aligned}$$

So

$$\begin{aligned}{} & {} SDE(X) = \sum _{u_i\in V(G_{1})}\sum _{v_jv_l\in E(G_{2})}\left[ \frac{\varepsilon _{G_{1}}(u_i)+\varepsilon _{G_{2}}(v_j)}{\varepsilon _{G_{1}}(u_i)+\varepsilon _{G_{2}}(v_l)} + \frac{\varepsilon _{G_{1}}(u_i)+\varepsilon _{G_{2}}(v_l)}{\varepsilon _{G_{1}}(u_i)+\varepsilon _{G_{2}}(v_j)}\right] \end{aligned}$$

(1)

$$\begin{aligned}{} & {} \qquad \qquad \qquad + \sum _{v_j\in V(G_{2})}\sum _{u_iu_k\in E(G_{1})}\left[ \frac{\varepsilon _{G_{1}}(u_i)+\varepsilon _{G_{2}}(v_j)}{\varepsilon _{G_{1}}(u_k)+\varepsilon _{G_{2}}(v_j)} + \frac{\varepsilon _{G_{1}}(u_k)+\varepsilon _{G_{2}}(v_j)}{\varepsilon _{G_{1}}(u_i)+\varepsilon _{G_{2}}(v_j)}\right] .\nonumber \\ \end{aligned}$$

(2)

In the second term, the edges between graphs $G_2$ are considered and it is clear that in these edges, the eccentricities of two ends of an edge have the same value. Therefore the second term is equal to $2n_2m_1$. Furthermore, consider that the function f by $f(x)=\frac{a+x}{a+(x+1)}+\frac{a+(x+1)}{a+x}$ is decreasing. This implies that the maximum value of this function occurs when the eccentricities of all vertices in $G_1$ are one, and in $G_2$, the eccentricities are 1 and 2, for each edge. Consequently, we have

$$\begin{aligned} SDE(G_{1}\times G_{2})&\le n_{1}\sum _{v_jv_l\in E(G_{2})}\left[ \frac{1+1}{1+2} + \frac{1+2}{1+1}\right] +2n_2m_1 \\&=\frac{13}{6} n_{1}m_2 + 2n_{2}m_1. \end{aligned}$$

$\square$

Theorem 3.2

Consider two graphs $G_1$ and $G_2$ of orders $n_1$ and $n_2$, respectively. Then

$$\begin{aligned}SDE(G_{1} \circ G_{2} ) \le SDE(G_1) + n_1SDE(G_2) + n_1n_2\left( \frac{13}{6}\right) .\end{aligned}$$

Equality holds if and only if $G_1 \cong K_{n_1}$.

Proof

The edges of the corona graph $G_{1} \circ G_{2}$ can be partitioned into three distinct subsets as follows:

$$\begin{aligned}{} & {} E_{1} = \left\{ e \in E(G_{1} \circ G_{2}), e \in E(G_{1})\right\} ,\\ {}{} & {} E_{2} = \left\{ e \in E(G_{1} \circ G_{2}), e \in E(G_{2_{i}}), i = 1,2,\ldots ,V(G_{1})\right\} ,\\ {}{} & {} E_{3} = \left\{ e \in E(G_{1} \circ G_{2}), e = uv, u \in V(G_{2_{i}}), i = 1,2,...,V(G_{1}), v \in V(G_{1})\right\} ,\end{aligned}$$

and

$$\begin{aligned}{} & {} \varepsilon _{G_{1} \circ G_{2}} (u) = {\left\{ \begin{array}{ll} \varepsilon (u) + 1 &{} \text {if } u \in V(G_{1}) \\ \varepsilon (u) + 2 &{} \text {if } u \in V(G_{2}) \end{array}\right. }.\end{aligned}$$

Then

$$\begin{aligned} \begin{array}{l} SDE\mathrm {(}G_{\textrm{1}}\circ G_{\textrm{2}}\mathrm {)}\mathrm {=}\sum _{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{uv\in E_{\textrm{1}}}}}}{}\left[ \frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v\mathrm {)}}+\frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u\mathrm {)}}\right] \\ \qquad \qquad \qquad \qquad \quad +\sum _{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{u'v'\in E_{\textrm{2}}}}}}{}\left[ \frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u'\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v'\mathrm {)}}+\frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v'\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u'\mathrm {)}}\right] \\ \qquad \qquad \qquad \qquad \quad +\sum _{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{u''v''\in E_{\textrm{3}}}}}}{}\left[ \frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u''\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v''\mathrm {)}}+\frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v''\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u''\mathrm {)}}\right] \\ \mathrm {=}\sum _{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{uv\in E_{\textrm{1}}}}}}{}\left[ \frac{{\varepsilon }_{G_{\textrm{1}}}\mathrm {(}u\mathrm {)}+\textrm{1}}{{\varepsilon }_{G_{\textrm{1}}}\mathrm {(}v\mathrm {)}+\textrm{1}}+\frac{{\varepsilon }_{G_{\textrm{1}}}\mathrm {(}v\mathrm {)}+\textrm{1}}{{\varepsilon }_{G_{\textrm{1}}}\mathrm {(}u\mathrm {)}+\textrm{1}}\right] \\ \qquad \qquad \qquad \qquad \quad +\sum _{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{u'v'\in E_{\textrm{2}}}}}}{}\left[ \frac{{\varepsilon }_{G_{\textrm{2}}}\mathrm {(}u'\mathrm {)}+\textrm{2}}{{\varepsilon }_{G_{\textrm{2}}}\mathrm {(}v'\mathrm {)}+\textrm{2}}+\frac{{\varepsilon }_{G_{\textrm{2}}}\mathrm {(}v'\mathrm {)}+\textrm{2}}{{\varepsilon }_{G_{\textrm{2}}}\mathrm {(}u'\mathrm {)}+\textrm{2}}\right] \\ \qquad \qquad \qquad \qquad +\sum _{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{u''v''\in E_{\textrm{3}}}}}}{}\left[ \frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u''\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v''\mathrm {)}}+\frac{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}v''\mathrm {)}}{{\varepsilon }_{G_{\textrm{1}}\circ G_{\textrm{2}}}\mathrm {(}u''\mathrm {)}}\right] \\ \le \sum _{{\ }_{{\ }_{{\ }_{uv\in E_1}}}}{}\left[ \frac{\varepsilon _{G_1}(u)}{\varepsilon _{G_1}(v)}+\frac{\varepsilon _{G_1}(v)}{\varepsilon _{G_1}(u)}\right] \\ \qquad \qquad \qquad \qquad \quad +n_{\textrm{1}}\sum _{{\ }_{{\ }_{{\ }_{u'v'\in E_2}}}}{}\left[ \frac{\varepsilon _{G_2}(u')}{\varepsilon _{G_2}(v')}+\frac{\varepsilon _{G_2}(v')}{\varepsilon _{G_2}(u')}\right] \\ \qquad \qquad \qquad \qquad \quad +\sum _{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{{\mathrm {\ }}_{u''v''\in E_{\textrm{3}},u''\in V_{\textrm{1}},v''\in V_{\textrm{2}}}}}}}}{}\left[ \frac{2}{3}+\frac{3}{2}\right] \\ \le SDE(G_1) + n_1SDE(G_2) + n_1n_2(\frac{13}{6}). \end{array} \end{aligned}$$

If $G_1 \cong K_{n_1}$, then clearly the equality holds. Conversely, if equality holds then all vertices of $G_1$ are adjacent and for each vertex $u \in V(G_1)$ and $v \in V(G_2)$, we have $\varepsilon _{G_1}(u)=2$ and $\varepsilon _{G_2}(v)=3$ and this completes the proof. $\square$

Proposition 3.1

Let G be a graph of order n, size m and t well-connected vertices. Then

$$\begin{aligned}SDE(G) ={\frac{1}{2} t(n-t)+2m}.\end{aligned}$$

Proof

Since the diameter of the graph is two, the eccentricity of each vertex is either one or two. Assume that the graph has t well-connected vertices. In this case, the following formula can be inferred:

$$\begin{aligned} SDE(G)&= t(n-t)\left( \frac{1}{2} +\frac{2}{1} \right) +\frac{t(t-1)}{2}\left( \frac{1}{1}+\frac{1}{1} \right) \\&\quad +\left( m-t(n-t)-\frac{t(t-1)}{2}\right) \left( \frac{2}{2} +\frac{2}{2}\right) \\&=\frac{1}{2} t(n-t)+2m. \end{aligned}$$

$\square$

Theorem 3.3

A graph G has diameter two, and all of its edges are nec if and only if $G \cong S_{n}$.

Proof

If $G \cong S_{n}$, it is evident that the conditions of the problem are satisfied. Let G be a graph with diameter two and all edges are nec. Therefore, there exist vertices like $w_{i}$ and $w_{j}$ such that there is a path of length two, such as $w_{i}, w_{k}, w_{j}$ between them. Therefore, $\varepsilon (w_{i})$, $\varepsilon (w_{k})$ and $\varepsilon (w_{j})$ are 2, 1, and 2, respectively and the degree of vertex $w_{k}$ is $n-1$. Suppose the vertex $w_{i}$ is adjacent to another vertex say $w_{t}$. If the eccentricity of $w_t$ is one, the edge $w_tw_k$ has an eccentricity of one at both ends which contradicts the assumption of the problem. If $\varepsilon (w_{t})=2$, then the eccentricity of both ends of $w_{i} w_{t}$ is two, a contradiction. We can conclude that a vertex like $w_{t}$ cannot exist, and except for $w_{k}$, the degree of other vertices is one and so $G \cong S_{n}$. $\square$

Note 1. It is not difficult to prove that every tree of order greater than 3, has at least three nec-edges.

Note 2. If a graph G has at least three distinct eccentricities, then G has at least three nec-edges.

Theorem 3.4

If G is nec-graph, then the diameter of the graph is even.

Proof

Let the diameter of graph G be d. Therefore, there exists a path, $v_1,v_2,v_3,\ldots ,v_{d+1}$, where all $\varepsilon (v_1)$, $\varepsilon (v_2)$, $\ldots$, $\varepsilon (v_{d+1})$ are distinct.

Knowing that two ends of an edge have either equal eccentricities or their difference is 1, we conclude $\varepsilon (v_1)=\varepsilon (v_{d+1})=d$ and $\varepsilon (v_2)=\varepsilon (v_{d})=d-1$. By using proof by contradiction, assume that the diameter of the graph is odd. In this case, we will show that along the path $v_1, v_2, v_3, \ldots , v_{d+1}$, there exists an edge e in the center, and the eccentricities of endpoints of e are the same.

As shown in Table 1, the possible values for the eccentricities of two ends of a median edge($v_{d+1/2}$, $v_{d-(d-3)/2}$), are as follows: when $(d+1)/2$ is odd, they are d, $d-2$, $d-4\ldots d-((d-3)/2+1)$ and when $(d+1)/2$ is even, the possible values are $d-1, d-3, d-5, \ldots , d-((d+1)/2-1)$. In both cases, the minimum difference is 2 and cannot represent the eccentricities of two ends of an edge. $\square$

Corollary 3.1

If a graph has diameter $d=2k+1$, then there exists at least one ec edge.

Corollary 3.2

There is no graph with diameter three, in which all edges are nec.

Theorem 3.5

There is no graph with exactly one nec-edge.

Proof

Suppose $e=uv$ is the only nec-edge. Assume P is the longest path containing e, where $P=w_1w_2 \ldots w_iuvw_{i+3} \ldots w_{d+1}$. Since, according to the assumption, all edges are ec-edge except e, we obtain

$$\begin{aligned} \varepsilon (w_1)= \varepsilon (w_2)= \ldots = \varepsilon (w_{i})=\varepsilon (u)=d, \end{aligned}$$

and neccesarily $\varepsilon (v)=d-1$. This means that

$$\begin{aligned} d-1=\varepsilon (v)= \varepsilon (w_{i+3})= \ldots = \varepsilon (w_{d+1}), \end{aligned}$$

a contradiction with $d(w_1,w_{d+1})=d$. $\square$

Table 1 The contribution of different eccentricities of vertices

Theorem 3.6

If the graph G has exactly two nec edges, then both of them are pendants.

Proof

Suppose G has two nec edges say $e=uv$ and $e'=u'v'$ and the other edges are ec. We demonstrate that the edges e and $e'$ are located on the longest path in the graph. Let $\varepsilon (u)=\alpha$, $\varepsilon (v)=\alpha -1$, $\varepsilon (u')=\beta$ and $\varepsilon (v')=\beta -1$. Since the graph is connected, there exists a path P between e and $e'$. All edges on P are ec, so we conclude that $\alpha =\beta$ and the eccentricity is either $\alpha$ or $\alpha -1$, for all vertices and the diameter of G is equal to $\alpha$. On the other hand, except for e and $e'$, all edges are ec, then the eccentricity of endpoints of an edge is either $\alpha$ or $\alpha -1$. However, if there are some edges where the eccentricity of their endpoints is $\alpha$ while in remaining edges it is $\alpha -1$, the graph structure will resemble Fig. 1, where the edges e and $e'$ are cut edges which contradicts the fact $\alpha$ is diameter. Therefore, the eccentricity of endpoints of all edges in the graph is either $\alpha$ or $\alpha -1$, but not both. If they are $\alpha$, then vertices $u'$ and $v'$ are not adjacent to any other vertex and their degree is 1. If the eccentricity of endpoints of all edges is $\alpha -1$, then vertices u and v are not adjacent to any other vertex and their degree is 1. $\square$

Fig. 1

The structure of the graph in Theorem 3.6

Theorem 3.7

Let G be a graph ($G \not \cong S_{n}$) with size $m \ge 4$ and diameter $d \ge 2$. Then

$$\begin{aligned} 2(m-2)+2(\frac{d}{d-1} +\frac{d-1}{d})\le SDE(G) \le \frac{5}{2} m -\frac{1}{2}. \end{aligned}$$

The equality holds for lower bound for $G+2e$, where G is a $\Theta$-graph and upper bound holds for two graphs $S_{m} +e$ and $(K_{\frac{m-1}{2} } )^{c} +K_{2}$.

Proof

For the lower bound, if G is not self-centered, then by Theorem 3.5, it has at least two pendant edges. If any rooted tree $T_v$ attached to a vertex of $C_n$ is of order greater than 3, then by Note 1 we have a contradiction. If $|T_v|=3$, then G is isomorphic with one of the graphs depicted in Fig. 2. $\square$ $\square$

Fig. 2

Graph G in Theorem 3.7

In Fig. 2a, G has more than two nec-edges, a contradiction. Suppose two pendant edges uw and vw are attached to $C_n$ at vertex w. Without loss of generality, we can suppose the eccentricity of u or v holds with vertex x. Thus two vertices adjacent with x have the same eccentricity equal $\epsilon (w)$ which yields at least three nec-edges, a contradiction.

Finally, suppose two pendant edges are attached to $C_n$ at different vertices such as x and y, see Fig. 2c.

Let w lies in a shortest xy-path, where $d(w,x)\le [\frac{n}{4}]$. It is clear that $\epsilon (w)=\frac{n}{2}$ while $d(w,u)= [\frac{n}{4}]+1$ or $d(w,v)= [\frac{n}{4}]+1$. Hence, three vertices u, x, w have distinct eccentricities, a contradiction. Thus the lower bond equality holds holds for the graph $G+2e$, where G is $\Theta$-graph.

For the upper bound, obviously, the difference between eccentricities of vertices located on an edge is zero or one. Suppose r denotes the radius of graph G and G has exactly k equi-centric edges, then

$$\begin{aligned}{} & {} SDE(G) = \sum _{uv\in E(G)}\left[ \frac{\varepsilon (u)}{\varepsilon (v)} +\frac{\varepsilon (v)}{\varepsilon (u)} \right] \nonumber \\{} & {} \quad \le 2+2+\cdots +2+(m-k)\left[ \frac{r}{r+1} +\frac{r+1}{r} \right] . \end{aligned}$$

(3)

Since the function f by $f(x)=\frac{x}{x+1} +\frac{x+1}{x}$ is decreasing, the maximum value of SDE occurs for $r=1$ and therefore

$$\begin{aligned}SDE(G) \le \frac{5}{2} m-\frac{k}{2}. \end{aligned}$$

It is clear that the maximum value of (1) occurs when $k=1$. In the following, we show that the equality holds for the upper bound in graphs isomorphic with one of the structures shown in Fig. 3. The graph G has exactly one ec-edge say uv. The values of $\varepsilon (v)$ and $\varepsilon (u)$ can be either one or two.

1) Assume that $\varepsilon (v)$ = $\varepsilon (u)$= 1 and consider an arbitrary vertex w. Suppose on the contrary that w is adjacent to a vertex z, then either the eccentricity of both ends of wz is two, a contradiction, or one of them is two and the other is one. Without loss of generality, suppose the eccentricity of vertex z is one. In this case, both ends of uz have the same eccentricity, a contradiction. This yields a graph with structure (a) as shown in Fig. 3.

2) Assume that $\varepsilon (v)$ = $\varepsilon (u)$= 2. There are two paths, namely $P_1=u,s,w$ and $P_2=v,t,z$. Since the eccentricity of u and v is two, the eccentricity of s and t must be one. Clearly, s and t are adjacent implying that the edge st is ec, a contradiction. Therefore, we conclude s and t can not be distinguished, and the desired paths are $P_1=u,s,w$ and $P_2=v,s,z$. Similarly, it is not difficult to see that two vertices w and z are not adjacent, and the graph has a structure as depicted in Fig. 3.7b.

Fig. 3

All structures of graphs given in Theorem 3.7

Example 3.1

It should be noted that there many classes of graphs satisfying the lower bound condition of Theorem 3.7, but among them, a $\Theta$-graph has the minimum number of edges. For example, two graphs Fig. 4 have exactly two nec-edges but graph Fig. 4a has 7 edges while Fig. 4b has 8 edges. To construct a class of graphs satisfying in the conditions of Theorem 3.7, we consider a cycle graph of length $2k+1$. Then, we add a path of length $k-1$ between two vertices in the cycle, namely $v_i$ and $v_{i+k}$. Finally, we add two pendant edges to vertices u and v. The structure of these graphs can be observed in Fig. 4c.

Fig. 4

The structure of graphs in Example 3.1

Theorem 3.8

Let G be a connected graph with size $m \ge 4$ and diameter $d=3$. Then

$$\begin{aligned}SDE(G) \ge \frac{13}{6} m -\frac{1}{6}.\end{aligned}$$

The equality holds for the bistar graph $S_{a,b}$.

Fig. 5

Bistar graph $S_{a,b}$: A graph structure showing equality in Theorem 3.8

Proof

Suppose the number of ec-edges is k, then according to Theorem 3.7, we have

$$\begin{aligned}\begin{array}{l} {SDE(G) \ge 2k+(m-k)\left[ \frac{d}{d-1} +\frac{d-1}{d} \right] }.\end{array}\end{aligned}$$

Considering $d=3$, the inequality can be rewritten as

$$\begin{aligned} {SDE(G) \ge 2k+(m-k)\left[ \frac{3}{2} +\frac{2}{3} \right] =2k+\frac{13}{6}(m-k)=\frac{13}{6}m-\frac{1}{6}k}. \end{aligned}$$

(4)

So, the minimum value of SDE(G) with diameter three is $\frac{13}{6}m-\frac{1}{6}$. In the following, we show all structures with equality in Eq. 4 are isomorphic with the bistar graph $S_{a,b}$. Since the diameter of G is three, there exists a path of length three say $P = w_1w_2w_3w_4$. Since $\varepsilon (w_1)$ = $\varepsilon (w_4)$= 3, $\varepsilon (w_2)$ and $\varepsilon (w_3)$ are 2 or 3. Since there is exactly one ec-edge, we conclude $\varepsilon (w_2)$ and $\varepsilon (w_3)$ are not three simultaneously. Therefore, either $\varepsilon (w_2)=\varepsilon (w_3)=2$ or $\varepsilon (w_2)=2$ and $\varepsilon (w_3)=3$.

1) At first suppose $\varepsilon (w_2)$ = $\varepsilon (w_3)$= 2. For each arbitrary vertex z, we have $\varepsilon (z) \ne 1$, because otherwise $d(w_1,w_4)=2$, a contradiction. Thus we may assume that $\varepsilon (z)=2$, then z is not adjacent to $w_2$ or $w_3$ and so it is adjacent to $w_1$ or $w_4$, but not both. Without loss of generality, assume that z is adjacent to $w_1$, then $d(z,w_4)>3$, a contradiction. Hence $\varepsilon (z)=3$ and thus z is not adjacent to $w_1$ or $w_4$. Suppose z is adjacent to both $w_2$ and $w_3$, there exists a path of the length of three from z to a vertex like s. If this path passes through $w_2$ or $w_3$, the structure (b) in Fig. 6 occurs and if $\varepsilon (t)=2$ then the edge $tw_3$ is ec. In the case that $\varepsilon (t)=3$, the edge ts is ec. If this path passes through $w_1$ or $w_4$, the structure (a) in Fig. 6 occurs and edge $w_4s$ is ec. Finally, if P does not contain vertices $w_1$, $w_2$, $w_3$ and $w_4$, then the structure (c) occurs in Fig. 6 and one of the edges ys or xy are ec. In all cases, the number of ec-edges is greater than one, a contradiction. $\square$

Fig. 6

Different positions of vertex s with respect to z

Table 2 Correlation analysis of SDE index with the topological indices

Hence, z is adjacent to one of the vertices $w_2$ or $w_3$. This implies that all vertices except $w_i's$ (i=1,2,3,4) have an eccentricity equal to three. If there are edges between these vertices, then the number of ec-edges is greater than two, a contradiction. Consequently, all of them are pendant edges and we are done.

4 Analyzing protein networks

Proteins play a crucial role in various biological processes and are often represented as networks to understand their structural and functional properties, see [2, 10, 11, 15]. In this section, we extend our investigation of SDE index by analyzing real protein networks.

Fig. 7

Scatter maps showing the relationship between SDE and different graph properties

Essential proteins play critical roles in cell processes such as development and survival. Table 2 reports the correlation coefficients between the SDE index and several graph invariants including the indepence number $\alpha =\alpha (G)$, $\vert LF \vert$, $\vert V \vert$, $\vert E \vert$, R, H, ABC, SC, $M_1$, $M_2$, and $\vert A\vert =\vert Aut(G) \vert$. Each correlation coefficient represents the strength and direction of the relationship between the SDE index and the corresponding network property. We observed a strong linear correlation between SDE and $M_2$ and R. In other words, upon analyzing the results, we infer that SDE index exhibits a strong positive correlation with $\vert E \vert$, $ABC, SC, M_1, \vert V \vert , \alpha , R, H$, and $M_2$, respectively. The implications of these correlation analysis results are significant for understanding protein network properties.

These findings can guide further research in protein network analysis and contribute to the development of more accurate computational models for predicting protein functions and identifying potential therapeutic targets. It evaluates whether the coefficients of all predictors collectively exhibit a significant deviation from zero. Overall, the correlation analysis between the SDE index and topological indices provides valuable insights into the intricate nature of protein networks. By unravelling the relationships between network properties, we can deepen our understanding of protein network organization and its implications in biological networks.

Table 3 Results of the linear regression model for the variables SDE, $\vert A \vert$, $M_2$, and R

In Table 3 the coefficient for $M_2$ is estimated as 0.05284 with a standard error of 0.0009274. It is highly statistically significant (p-value < 2$e-16$), implying that $M_2$ has a strong positive impact on SDE. For a one-unit increase in $M_2$, SDE is expected to increase by approximately 0.05284 units, while keeping all other variables constant. The coefficient for R is estimated as 3.743 with a standard error of 0.01499. It is highly statistically significant (p-value <2$e-16$), indicating that R has a strong positive impact on SDE. For a one-unit increase in R, SDE is expected to increase by approximately 3.743 units, while keeping all other variables constant. The coefficient for $\vert A \vert$ is estimated as $-$7.136$e-256$ (which is essentially zero) with a standard error of 0. The coefficient being effectively zero suggests that $\vert A \vert$ may not be contributing significantly to the model, and its inclusion in the regression equation may not be appropriate. Therefore, we remove $\vert A \vert$ and perform the regression again.

Table 4 Results of the linear regression model for the variables SDE, $M_2$, and R

Table 5 Exploring the topological indices of a collection of 42 proteins

Table 6 Exploring the topological indices of a collection of 42 proteins

In Table 4 the estimated coefficient for $M_2$ is 2.983$e-02$. It indicates that a one unit increase in $M_2$ is associated with an estimated increase of 0.02983 units in the predicted value of SDE. The estimated coefficient for R is 4.010e+00. This suggests that a one-unit increasing in R is associated with an estimated increase of 4.01 units in the predicted value of SDE. The R-squared is 0.995, meaning that approximately 99.5 percent of the variability in SDE can be explained by the independent variables ($M_2$ and R) included in the model. The adjusted R-squared (Adjusted R-squared) is 0.9947, which is slightly lower than the R-squared value but still indicates a highly effective model in explaining the relationship between SDE and the predictors. The F-statistic tests the overall significance of the regression model. It assesses whether the coefficients of all predictors are jointly different from zero. In this case, the F-statistic is 3872 with degrees of freedom (DF) of 2 and 39. The associated p-value is $< 2.2e-16$, which is extremely low. This suggests that the overall regression model is highly significant, indicating that at least one of the predictors ($M_2$ or R) is significantly related to SDE. In summary, the regression analysis indicates that both $M_2$ and R are highly significant predictors of SDE. The model explains a large proportion of the variability in SDE, as evident from the high R-squared value. The overall regression model is also highly significant, suggesting that it provides valuable information for predicting and understanding the relationship between SDE and the predictors. The regression equation for the variables SDE, $M_2$, and R, as shown in Table 4, can be written as:

$$\begin{aligned} SDE = 201.4 + 0.02983M_2 + 4.01R. \end{aligned}$$

5 Conclusion

In this article, we introduced the SDE index as a new version of the SDD-index in graphs, which utilizes eccentricity instead of vertex degrees for graph analysis. Through our investigation, we determined the limits of the SDE index and explored its relationship with other graph properties. We have found significant correlations between SDE and various graph properties. Furthermore, the strong positive associations between SDE and indices like R and H suggest the central and diverse roles played by proteins with higher SDE values in the network. Additionally, the nearly perfect correlation between SDE and the ABC index emphasizes the crucial involvement of proteins with high SDE values. Regression analysis confirms the significance of $M_2$ and R as predictors for SDE, with the model explaining a substantial proportion of its variability. Overall, our findings contribute to advancing graph analysis and understanding the intricate interplay between SDE and other graph characteristics.