# Edge-Neighbor-Rupture Degree of Graphs

Authors: Ersin Aslan
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The edge-neighbor-rupture degree of a connected graphG is defined to be ENRG=maxωG−S−S−mG−S:S⊆EG,ωG−S≥1, where S is any edge-cut-strategy of G, ωG−S is the number of the components of G−S, and mG−S is the maximum order of the components of G−S. In this paper, the edge-neighbor-rupture degree of some graphs is obtained and the relations between edge-neighbor-rupture degree and other parameters are determined.


---

## Body

## 1. Introduction

In a communication network, the vulnerability measures the resistance of the network to disruption of operation after the failure of certain stations or communication links. To measure the vulnerability we have some parameters which are connectivity [1], integrity [2], scattering number [3], and rupture degree [4].A spy network can be modeled by a graph whose vertices represent the stations and whose edges represent the lines of communication. If a station is destroyed, the adjacent stations will be betrayed so that the betrayed stations become useless to network as a whole [5]. Therefore, instead of considering the stability of a communication network in standard sense, some new graph parameters such as vertex-neighbor-connectivity [6] and edge-neighbor-connectivity [7], vertex-neighbor-integrity [8] and edge-neighbor-integrity [9], vertex-neighbor-scattering number [10] and edge-neighbor-scattering number [11], and vertex-neighbor-rupture degree [12] were introduced to measure the stability of communication networks in “neighbor” sense.We use Bondy and Murty [1] for terminology and notation not defined here and consider only finite simple connected graphs. Let G=(V,E) be a graph and e any edge in G.The diameter of  G, denoted by diam(G), is the maximum distance over all pairs of vertices in G.N
(
e
)
=
{
f
∈
E
(
G
)
∣
f
≠
e
;
e and f are adjacent} is the open-edge-neighborhood of e, and N[e]=N(e)∪{e} is the closed-edge-neighborhood of e. An edge e in G is said to be subverted when N[e] is deleted from G. In other words, if e=[u,v], G-N[e]=G-{u,v}. A set of edges S is called an edge subversion strategy of G if each of the edges in S has been subverted from G. The survival subgraph is denoted by G-S. An edge subversion strategy S is called an edge-cut-strategy of G if the survival subgraph G-S is disconnected or is a single vertex or the empty graph [13].The edge-neighbor-connectivity ofG,Λ(G), is the minimum size of all edge-cut-strategies of G. A graph G is m-edge-neighbor-connected if Λ(G)=m [7].The edge-neighbor-integrity of a graphG,ENI(G), is defined to be
(1)ENI(G)=minS⊆E(G){|S|+m(G-S)},
where S is any edge subversion strategy of G and m(G-S) is maximum order of the components of G-S  [9].The edge-neighbor-scattering number ofG, ENS(G), is defined as
(2)ENS(G)=maxS⊆E(G){ω(G-S)-|S|},
where S is any edge-cut-strategy of G and ω(G-S) is the number of the components of G-S [11].The known parameters concerning the neighborhoods do not deal with the number of the removing edges, the number of the components, and the number of the vertices in the largest component of the remaining graph in a disrupted network simultaneously. In order to fill this void in the literature, the current study proposes a definition of edge-neighbor-rupture degree which is a new parameter concerning these three values. Additionally, this study also analyzes the relations between edge-neighbor-rupture degree and some other  parameters and obtains edge-neighbor-rupture degree of some graphs.The edge-neighbor-rupture degree of a connected graphG is defined to be
(3)ENR(G)=max{ω(G-S)-|S|-m(G-S):S⊆E(G),ω(G-S)≥1},
where S is any edge-cut-strategy of G, ω(G-S) is the number of the components of G-S, and m(G-S) is the maximum order of the components of G-S. A set S*⊆E(G) is said to be the ENR-set of G if ENR(G)=ω(G-S*)-|S*|-m(G-S*).The edge-neighbor-rupture degree differs from edge- neighbor-connectivity, edge-neighbor-integrity, and edge-neighbor-scattering number in showing the vulnerability of networks. For example, consider the graphsG1 and G2 in Figure 1.The graphsG1 and G2.
(a)
(b)It can be easily seen that the edge-neighbor-connectivity, edge-neighbor-integrity, and edge-neighbor-scattering number of these graphs are equal:(4)Λ(G1)=Λ(G2)=1,ENI(G1)=ENI(G2)=4,ENS(G1)=ENS(G2)=4.On the other hand, the edge-neighbor-rupture degrees ofG1 and G2 are different:
(5)ENR(G1)=1,ENR(G2)=2.Hence, the edge-neighbor-rupture degree is a better parameter for distinguishing vulnerability of graphsG1 and G2.


## 2. Bounds for Edge-Neighbor-Rupture Degree

In this section some lower and upper bounds are given for the edge-neighbor-rupture degree of a graph using different graph parameters.Theorem 1.
LetG be a connected graph of order n. Then,
(6)ENR(G)≤n-4.Proof.
LetS be an edge-cut-strategy of G and |S|=r. If r≥1, then ω(G-S)≤n-2 and m(G-S)≥1. Therefore,
(7)ω(G-S)-|S|-m(G-S)≤n-2-1-1.
Hence we have(8)ENR(G)≤n-4.
The proof is completed.Theorem 2.
LetG be a connected graph of order n, and let α(G), Λ(G) be the independent number and edge-neighbor-connectivity of G, respectively. Then,
(9)ENR(G)≤α(G)-Λ(G)-1.Proof.
LetS be an edge-cut-strategy of G.  For any S of G, |S|≥Λ(G),ω(G-S)≤α(G), and m(G-S)≥1. Hence we get
(10)ENR(G)≤α(G)-Λ(G)-1.
The proof is completed.Theorem 3.
LetG be a connected graph of order n≥3. If ENR(G)=n-4; then diam(G)≤3.Proof.
Assume thatdiam(G)≥4; then G contains a path P5. Thus for any edge e in G, ω(G-S)≤n-2, m(G-{e})≥2, and for any two edges e1 and e2 in G, ω(G-e)≤n-2, m(G-{el,e2})≥1. Therefore
(11)ENR(G)≤n-5,
a contradiction. Hence diam(G)≤3.
The proof is completed.Theorem 4.
LetG be a connected graph of order n and α′(G) edge independence number of G. Then,
(12)ENR(G)≤n-3α′(G)-1.Proof.
LetS be an edge-cut-strategy of G.  If |S|=α′(G), then  G-S contains n-2α′(G) isolated vertices  and m(G-S)≥1. From the definition of edge neighbor rupture degree we have
(13)ENR(G)≤n-3α′(G)-1.
The proof is completed.


## 3. Edge-Neighbor-Rupture Degree of Some Graphs

In this section, we consider the edge-neighbor-rupture degree of some graphs.Theorem 5.
LetPn be a path with order n(≥4). Then
(14)ENR(Pn)={0,n≡1(mod3),-1,n≡0,2(mod3).Proof.
LetS be an edge-cut-strategy of Pn and |S|=r. If  r≤⌊(n-1)/3⌋, then ω(Pn-S)≤r+1 and m(Pn-S)≥⌈(n-2r)/(r+1)⌉. Thus
(15)ω(Pn-S)-|S|-m(Pn-S)≤r+1-r-⌈n-2rr+1⌉ENR(Pn)≤maxr{1-⌈n-2rr+1⌉},
the function f(r) takes its maximum value at r=⌊(n-1)/3⌋, and we get ENR(Pn)≤-1 where n≡0,2(Mod3) and ENR(Pn)≤0 where n≡1(Mod3). So, we have
(16)ENR(Pn)≤{0,n≡1(mod3),-1,n≡0,2(mod3).
On the other hand, ifr≥⌊(n-1)/3⌋+1, then we have ω(Pn-S)≤r and m(Pn-S)≥1. Hence
(17)ω(Pn-S)-|S|-m(Pn-S)≤r-r-1,ENR(Pn)≤-1.
It can be easily seen that there is an edge-cut-strategyS* of Pn such that |S*|=⌊(n-1)/3⌋, ω(Pn-S*)=⌊(n-1)/3⌋+1, and m(Pn-S*)=2 where n≡0,2(Mod3) and m(Pn-S*)=1  where n≡1(Mod3). Therefore,
(18)ENR(Pn)={0,n≡1(mod3),-1,n≡0,2(mod3).
The proof is completed by (16), (17), and (18).Theorem 6.
LetCn be a cycle with order n(≥6). Then
(19)ENR(Cn)={-1,n≡0(mod3),-2,n≡1,2(mod3).Proof.
LetS be an edge-cut-strategy of Cn and |S|=r. If  r≤⌊n/3⌋, then ω(Cn-S)≤r and m(Cn-S)≥⌈(n-2r)/r⌉. Thus
(20)ω(Cn-S)-|S|-m(Cn-S)≤r-r-⌈n-2rr⌉,ENR(Cn)≤maxr{⌈n-2rr⌉},
the function f(r) takes its maximum value at r=⌊n/3⌋, and we get ENR(Cn)≤-1 where n≡0(Mod3)  and ENR(Cn)≤-2 where n≡1,2(Mod3). So, we have
(21)ENR(Cn)≤{-1,n≡0(mod3),-2,n≡1,2(mod3).
On the other hand, ifr≥⌊n/3⌋+1, then we have ω(Cn-S)≤r-1 and m(Cn-S)≥1. Hence
(22)ω(Cn-S)-|S|-m(Cn-S)≤r-1-r-1ENR(Cn)≤-2.
It can be easily seen that there is an edge-cut-strategyS* of Cn such that |S*|=⌊n/3⌋,ω(Cn-S*)=⌊n/3⌋, and m(Cn-S*)=2 where n≡1,2(Mod3) and m(Cn-S*)=1  where n≡0(Mod3). Therefore
(23)ENR(Cn)={-1,n≡0(mod3),-2,n≡1,2(mod3).
The proof is completed by (21), (22), and (23).Lemma 7 (see [7]).
For any graphG with order n, Λ(G)≤⌊n/2⌋.Theorem 8.
LetKn be a complete graph  with order n. Then
(24)ENR(Kn)=-⌊n2⌋.Proof.
LetS be an edge-cut-strategy of Kn  and |S|=r. By Lemma 7 we know Λ(Kn)=⌊n/2⌋. If  r≥⌊n/2⌋, then ω(Kn-S)≤1 and m(Kn-S)≥1. Hence,
(25)ω(Kn-S)-|S|-m(Kn-S)≤1-⌊n2⌋-1,ENR(Kn)≤-⌊n2⌋.
It can be easily seen that there is an edgesetS* of Kn such that |S*|=⌊n/2⌋, then we have ω(Kn-S)=1 and m(Kn-S)=1. From the definition of edge-neighbor-rupture degree we have
(26)ENR(Kn)=-⌊n2⌋.
The proof is completed.Definition 9.
We also callK1,n a star with n+1 vertices. Let DS(nl,n2) be a double star with {nl,n2} end-vertices, where n1≥0 and n2≥0, and a common edge [u,v], as shown in Figure 2. Note that if either n1 or n2 is 0, then the double star DS(nl,n2) is a star.Figure 2
DS
(
n
l
,
n
2
).Theorem 10.
LetT be a tree of order n≥4. Then ENR(T)=n-4 if and only if T is either a star K1,n-1 or a double star DS(nl,n2), where n1≥1, n2≥1, and n1+n2=n-2.Proof.
IfT is a tree of order n≥3 and ENR(T)=n-4, then by Theorem 3 we have either diam(T)=2 or diam(T)=3. If diam(T)=2, then  T is a star K1,n-1. If diam(T)=3, then T is a double star DS(nl,n2), where n1>0, n2>0, and n1+n2=n-2.
Conversely, letT be either a star K1,n-1 with the order n≥4 or a double star DS(nl,n2), where n1≥1, n2≥1, and n1+n2+2=n≥4.
IfS is an edge-cut-strategy of K1,n-1 and |S|=1, then we have n-2 isolated vertices. Therefore we have ω(T-S)=n-2 and m(T-S)=1. So
(27)ω(K1,n-1-S)-|S|-m(K1,n-1-S)=n-2-1-1ENR(K1,n-1)=n-4.
It can be easily seen that there is an edge-cut-strategyS* of DS(nl,n2)  such that |S*|=1; then we have ω(DS(nl,n2)-S*)=n-2 and m(DS(nl,n2)-S*)=1. So
(28)ω(DS(nl,n2)-S*)-|S*|-m(DS(nl,n2)-S*)=n-2-1-1,ENR(DS(nl,n2))=n-4.
IfS is an edge set of DS(nl,n2) and |S|>1, then we have ω(DS(nl,n2)-S)=1 and m(DS(nl,n2)-S)≥2.
The proof is completed.Theorem 11.
LetKm,n   be a complete bipartite graph with |m-n|≥1. Then
(29)ENR(Km,n)={m-2n-1,ifm>n,n-2m-1,ifm<n.Proof.
Assumem>n.Let S be an edge-cut-strategy of Km,n  and |S|=r. If  r≥n, then ω(Km,n-S)≤m-n and m(Km,n-S)≥1. Hence,
(30)ω(Km,n-S)-|S|-m(Km,n-S)≤m-n-r-1,
the function f(r) is a decreasing function and takes its maximum value at r=n, and we get
(31)ENR(Km,n)≤m-2n-1.
It can be easily seen that there is an edge setS* of Km,n such that |S*|=n; then we have ω(Km,n-S)=m-n and m(Km,n-S)=1. From the definition of edge neighbor rupture degree we have
(32)ENR(Km,n)=m-2n-1.
Similarly, we obtainENR(Km,n)=n-2m-1 when n>m.
Finally, we have(33)ENR(Km,n)={m-2n-1,ifm>n,n-2m-1,ifm<n.
The proof is completed.Definition 12.
The wheel graph withn spokes, Wn, is the graph that consists of an  n-cycle and one additional vertex, say u, that is adjacent to all the vertices of the cycle. In Figure 3, we display W6.Figure 3
The wheel graphW6.Theorem 13.
LetWn be a wheel graph with order n(≥5). Then
(34)ENR(Wn)={-1,n≡2(mod3),-2,n≡0,1(mod3).Proof.
The graphWn has subgraphs Cn and K1,n. Let e be any one edge of K1,n.
Ife∈S and |S|=1, then we get  ω(Wn-S)=Pn-1.So,(35)ENR(Wn)=ENR(Pn-1)-1.
Ife∉S and |S|=1, then ω(Wn-S)=1 and m(Wn-S)≥2. Hence,
(36)ENR(Wn)≤ω(Wn-S)-|S|-m(Wn-S)≤1-1-2=-2.
Ife∉S and |S|≥2, then ω(Wn-S)=1 and m(Wn-S)≥1. Thus,
(37)ENR(Wn)≤ω(Wn-S)-|S|-m(Wn-S)≤1-2-1=-2.
The proof is completed by (35), (36), and (37).



---

*Source: 783610-2013-09-04.xml*