# Graph Operations and Neighbor Rupture Degree

Authors: Saadet Kandİlcİ; Goksen Bacak-Turan; Refet Polat
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

In a communication network, the vulnerability parameters measure the resistance of the network to disruption of operation after the failure of certain stations or communication links. A vertex subversion strategy of a graphG, say S, is a set of vertices in G whose closed neighborhood is removed from G. The survival subgraph is denoted by G/S. The neighbor rupture degree of G, Nr(G), is defined to be Nr(G)=max{w(G/S)-|S|-c(G/S):S⊂V(G),w(G/S)≥1}, where S is any vertex subversion strategy of G, w(G/S) is the number of connected components in G/S and c(G/S)  is the maximum order of the components of G/S (G. Bacak Turan, 2010). In this paper we give some results for the neighbor rupture degree of the graphs obtained by some graph operations.


---

## Body

## 1. Introduction

A network can be broke down completely or partially with unexpected reasons. If the data is not transmitted to the desired location that means there is a problem on the system. This problem can block a treaty of billions of euros or make a big problem for human’s life. In these days the reliability and the vulnerability of networks are so important. For that reason graphs are taken as a model in the research area of reliability and vulnerability of the networks. Each network center is taken as a vertex and the connections of these vertices are edges of a graph.A few questions can be asked at this point How can the reliability and the vulnerability of a network be determined? What are the factors of the reliability and the vulnerability? For example, what can be done if there is a problem on the way you are using every day to work? We have two choices; we may give up going to work although we have the risk of dismissal or we can look for another way to work. The question “if there is another way to reach work” may come to our minds. In other words “Has the link connection between home and work completely broken down?”. To answer this question, we must know the dimensions of the problem between home and work. The vulnerability of the graph which represents the way between home and work should be searched. In graph theory some vulnerability parameters are defined to measure the vulnerability value of graphs such as connectivity [1], integrity [2], neighbor integrity [3], rupture degree [4], and neighbor rupture degree [5].Terminology and notation not defined in this paper can be found in [5]. Let G be a simple graph and let u be any vertex of G. The set N(u)={v∈V(G)∣v≠u;vanduareadjacent} is the open neighborhood of u, and N[u]={u}∪N(u) is the closed neighborhood of u. A vertex u in G is said to be subverted if the closed neighborhood of u is removed from G. A set of vertices S={u1,u2,…,um} is called a vertex subversion strategy of G if each of the vertices in S has been subverted from G. If S has been subverted from the graph G, then the remaining graph is called survival graph, denoted by G/S.


## 2. Basic Results

In this paper the new vulnerability parameter neighbor rupture degree was studied. The concept of neighbor rupture degree was introduced by Bacak-Turan and Kırlangıc in 2011 [5]. The definition of neighbor rupture degree and some results are given below.Definition 1 (see [6]).
The neighbor rupture degree of a noncomplete connected graphG is defined to be
(1)Nr(G)=max{w(GS)-|S|-c(GS):S⊂V(G),w(GS)≥1},
where S is any vertex subversion strategy of G, w(G/S) is the number of connected components in G/S, and c(G/S) is the maximum order of the components of G/S.In particular, the neighbor rupture degree of a complete graphKn is defined to be Nr(Kn)=1-n. A set S⊂V(G) is said to be Nr-set of G if
(2)Nr(G)=w(GS)-|S|-c(GS).
Some known results are listed below.Theorem 2 (see [6]).
(a) LetPn be a path graph with n vertices and n≥2,
(3)Nr(Pn)={0,n≡1(mod4)-1,n≡0,2,3(mod4).
(b) LetCn be a cycle graph with n vertices and n≥3,
(4)Nr(Cn)={-1,n≡0(mod4)-2,n≡1,2,3(mod4).
(c) LetKn1,n2,n3,…,nk be a k-partite graph
(5)Nr(Kn1,n2,…,nk)=max{n1,n2,n3,…,nk}-3.
(d) LetWn be a wheel graph with n vertices and n≥5,
(6)Nr(Wn)={-1,n≡1(mod4)-2,n≡0,2,3(mod4).


## 3. Graph Operations and Neighbor Rupture Degree

In this section some graph operations are operated on graphs and their neighbor rupture degrees are evaluated.Definition 3 (see [7]).
The union graphG=G1∪G2∪⋯∪Gn has vertex set V(G)=V(G1)∪V(G2)∪⋯∪V(Gn) and edge set E(G)=E(G1)∪E(G2)∪⋯∪E(Gn). If a graph G consists of k(k≥2) disjoint copies of a graph H, then we write G=kH.Theorem 4.
LetG1,G2,G3,…,Gn be connected graphs. Then
(7)Nr(G1∪G2∪⋯∪Gn)00≥Nr(G1)+Nr(G2)+⋯+Nr(Gn).Proof.
LetG=G1∪G2∪⋯∪Gn be the union of G1,G2,…,Gn. Let S1,S2,…,Sn be Nr-sets of G1,G2,…,Gn respectively, and let S=S1∪S2∪⋯∪Sn be a subversion strategy of G. Then we obtain
(8)Nr(G)≥w(G(S1∪S2∪⋯∪Sn))-|S1∪S2∪⋯∪Sn|-c(G(S1∪S2∪⋯∪Sn))=w(G1S1)+w(G2S2)+⋯+w(GnSn)-|S1|-|S2|-⋯|Sn|-max{c(G1S1),c(G2S2),…,c(GnSn)}≥w(G1S1)+w(G2S2)+⋯+w(GnSn)-|S1|-|S2|-⋯|Sn|-c(G1S1)-c(G2S2)-⋯-c(GnSn)=Nr(G1)+Nr(G2)+Nr(G3)+⋯+Nr(Gn).
Thus we have Nr(G1∪G2∪⋯∪Gn)≥Nr(G1)+Nr(G2)+⋯+Nr(Gn).Theorem 5.
LetKn1,Kn2,…,Knm be complete graphs with n1≤n2≤nm where ni+1-ni≥2;∀i∈Z+. Then
(9)Nr(Kn1∪Kn2∪⋯∪Knm)=2-m-n1.Proof.
LetS be a subversion strategy of Kn1∪Kn2∪⋯∪Knm. Since these are complete graphs, it is obvious that S contains at most one vertex from each KnI˙.
If|S|=k, then w((Kn1∪Kn2∪⋯∪Knm)/S)=m-k and c((Kn1∪Kn2∪⋯∪Knm)/S)≥nm-k. Thus we have w((Kn1∪Kn2∪Kn3∪⋯∪Knm)/S)-|S|-c((Kn1∪Kn2∪Kn3∪⋯∪Knm)/S)≤m-2k-nm-k≤m-2k-n1-2(m-k-1) since
(10)ni+1-ni≥2,nm-k≥n1+2(m-k-1)=2-m-n1⟹Nr≤2-m-n1.
There exist S* such that |S*|=m-1, w((Kn1∪Kn2∪⋯∪Knm)/S*)=1 and c((Kn1∪Kn2∪⋯∪Knm)/S*)=n1. Then we have
(11)w((Kn1∪Kn2∪⋯∪Knm)S*)-|S*|-c((Kn1∪Kn2∪⋯∪Knm)S*)=2-m-n1⟹Nr≥2-m-n1.
From (10) and (11) we obtain Nr(Kn1∪Kn2∪⋯∪Knm)=2-m-n1.The following theorem’s proof is very similar to that of Theorem5.Theorem 6.
LetKn1,Kn2,Kn3,…,Knm be complete graphs with n1≤n2≤n3⋯≤nm where ni+1-ni≤2;  for all i∈Z+. Then
(12)Nr(Kn1∪Kn2∪Kn3∪⋯∪Knm)=m-nm.Corollary 7.
Let(13)Nr(Kn∪Km)={2-n,2>n-m,-m,otherwise.Definition 8 (see [7]).
The join graphG=G1+G2 has vertex set V(G)=V(G1)∪V(G2) and edge set E(G)=E(G1)∪E(G2)∪{uv∣u∈V(G1)andv∈V(G2)}.In this part, neighbor rupture degree of join of some graphs is given.Theorem 9.
LetG1 and G2 be two connected graphs. Then
(14)Nr(G1+G2)=max{Nr(G1),Nr(G2)}.Proof.
LetS be a subversion strategy of G1+G2. There are three cases according to the elements of S.
Case
1. Let S=S1⊂V(G1) be the Nr-set of G1 such that w(G1/S1)-|S1|-c(G1/S1)=Nr(G1). Since any elements from G1 are adjacent to every element of G2 in G1+G2, we have
(15)w(G1+G2S1)-|S1|-c(G1+G2S1)=w(G1S1)-|S1|-c(G1S1)=Nr(G1).
Case
2. Let S=S2⊂V(G2) be the Nr-set of G2 such that w(G2/S2)-|S2|-c(G2/S2)=Nr(G2). Since any elements from G2 are adjacent to every element of G1 in G1+G2, we have
(16)w(G1+G2S2)-|S2|-c(G1+G2S2)=w(G2S2)-|S2|-c(G2S2)=Nr(G2).
Case
3. Let S⊂V(G1)∪V(G2). Since S contains at least one vertex of V(G1) which is adjacent to all the vertices of V(G2) and S contains at least one vertex of V(G2) which is adjacent to all the vertices of V(G1) in G1+G2, then (G1+G2)/S is empty. It contradicts to the definition of neighbor rupture degree.
By (15) and (16) Nr(G1+G2)=max{Nr(G1),Nr(G2)}.For three or more disjoint graphsG1,G2,G3,…,Gn sequential join G1+G2+⋯+Gn is the graph (G1+G2)∪(G2+G3)∪⋯∪(Gn-1+Gn) [8].The following theorem’s proof is very similar to that of Theorem9.Theorem 10.
LetG1, G2, and G3 be connected graphs. Then the neighbor rupture degree of sequential join of  G1, G2, and G3 is
(17)Nr(G1+G2+G3)=max{Nr(G1∪G3),Nr(G2)}.Corollary 11.
IfG2≅Kn, then
(18)Nr(G1+G2+G3)≥Nr(G1)+Nr(G3).Corollary 12.
Ifn1≤n2≤n3, then
(19)Nr(Kn1+Kn2+Kn3)=-n3.Definition 13 (see [9]).
The complement of a simple graphG is obtained by taking the vertices of G and joining two of them whenever they are not joined in G and denoted by Gc.Theorem 14.
LetPn be a path graph of order n. Then
(20)Nr(Pnc)=-1.Proof.
LetS be a subversion strategy of Pnc and let S={u} where u∈V(Pn).
Case
1.   If deg(u)=1 in Pn, then u is adjacent to all vertices in Pnc except its neighbor in Pn. It means |N[u]|=n-1 in  Pnc, then we have
(21)w(PncS)-|S|-c(PncS)=1-1-1=-1.
Case
2.   If deg(u)=2 in Pn, then u is adjacent to all vertices in Pnc except its neighbors in Pn. It means |N[u]|=n-2 in Pnc  where the remaining two vertices are adjacent. Therefore,
(22)w(PncS)-|S|-c(PncS)=1-1-2=-2.
On the other hand, if we assume S is a subversion strategy with |S|≥2, then the remaining graph is empty. Therefore it contradicts to the definition of neighbor rupture degree.
From (21) and (22) we have Nr(Pnc)=-1.The following theorem’s proof is very similar to that of Theorem14.Theorem 15.
LetW1,n be a wheel graph of order n+1. Then
(23)Nr(W1,nc)=-1.Theorem 16.
LetKm,n be a complete bipartite graph. Then
(24)Nr(Km,nc)={2-n,2>n-m,-m,otherwise.Proof.
It is obvious thatKm,nc=Km∪Kn.
According to Corollary7 we get the result.Corollary 17.
LetK1,n be a star graph of order n+1. Then
(25)Nr(K1,nc)=-1.Definition 18 (see [7]).
The cartesian productG=G1×G2 has V(G)=V(G1)×V(G2), and two vertices (u1,u2) and (v1,v2) of G are adjacent if and only if either
(26)u1=v1,u2v2∈E(G2)
or
(27)u2=v2,u1v1∈E(G1).Theorem 19.
LetP2×P3a be a cartesian product with a∈Z+. Then
(28)Nr(P2×P3a)=a-1.Proof.
LetS be a subversion strategy of P2×P3a and |S|=r. There are two cases according to the number of elements in S.
Case
1. Let 1≤r≤a. Then N[S]≤4r and w≤2r.
Sincec((P2×P3a)/S)≥(|V(S)|-|N(S)|)/w≥((2.(3a)-4r)/2r)=3a/r-2 and
(29)w(P2×P3aS)-|S|-c(P2×P3aS)≤2r-r-(3ar-2)=r+2-3ar.
Let f(r)=r+2-3a/r. f is an increasing function since f′(r)=1+3a/r2>0. So it takes its maximum value at r=a. Then f(a)=a-3a/a+2=a-1. Hence,
(30)Nr(P2×P3a)≤a-1.
Case
2. Let a≤r≤|V(P2×P3a)|. Then c((P2×P3a)/S)≥1 and w((P2×P3a)/S)≤2(3a)-4a-(r-a)=3a-r, thus we obtain w((P2×P3a)/S)-|S|-c((P2×P3a)/S)≤3a-r-r-1=3a-2r-1.
Letf(r)=3a-2r-1. Since f′<0, f is a decreasing function, so it takes its maximum value at r=a. Then f(a)=3a-2a-1=a-1(31)Nr(P2×P3a)≤a-1.
From (30) and (31) we have
(32)Nr(P2×P3a)≤a-1.
It is obvious that there exist S* such that |S*|=a, w((P2×P3a)/S*)=2a and c((P2×P3a)/S*)=1 so
(33)Nr(P2×P3a)≥a-1.
From (32) and (33) we have Nr(P2×P3a)=a-1.The following theorems’ proofs are very similar to that of Theorem19.Theorem 20.
LetP2×P3a+1 be a cartesian product with a∈Z+. Then
(34)Nr(P2×P3a+1)=a-2.Theorem 21.
LetP2×P3a+2 be a cartesian product with a∈Z+. Then
(35)Nr(P2×P3a+2)=a-1.Theorem 22.
LetKm and Kn be two complete graphs with (m≤n). Then
(36)Nr(Km×Kn)=1-n.Proof.
LetS be a subversion strategy of Km×Kn and let |S|=r. We have two cases according to the cardinality of S.
Case
1. If 0≤r<m-1, then w((Km×Kn)/S)=1 and c((Km×Kn)/S)≥(m-r)(n-r), so we have
(37)w(Km×KnS)-|S|-c(Km×KnS)≤1-r-(m-r)(n-r).
Let f(r)=1-r-mn+(m+n)r-r2. Since f(r) is an increasing function in (0,m-1), it takes its maximum value at r=m-1 and f(m-1)=1-n. Thus we get
(38)Nr(Km×Kn)≤1-n.
Case
2. If m-1≤r≤(m-1)(n-1), then w((Km×Kn)/S)=1 and c((Km×Kn)/S)≥n-m+1. So we have w((Km×Kn)/S)-|S|-c((Km×Kn)/S)≤1-r-(n-m+1)=m-n-r.
Letf(r)=m-n-r. Since f(r) is a decreasing function, it takes its maximum value at r=m-1 and f(m-1)=1-n. Thus we get
(39)Nr(Km×Kn)≤1-n.
From (38) and (39) we have
(40)Nr≤1-n.
There exist S* such that r=m-1, w((Km×Kn)/S*)=1 and c((Km×Kn)/S*)=n-m+1, thus we have
(41)Nr≥1-n.
From (40) and (41) we get Nr=1-n.Definition 23 (see [9]).
The tensor productG1⊗G2 of two simple graphs G1 and G2 is the graph with V(G1⊗G2)=V1×V2 and where in (u1,u2) and (v1,v2) are adjacent in G1⊗G2 if, and only if, u1 is adjacent to v1 in G1 and u2 is adjacent to v2 in G2.Theorem 24.
LetP3⊗Pn be a tensor product of P3 and Pn  and n≡0(mod4). Then
(42)Nr(P3⊗Pn)=n-1.Proof.
LetS be a subversion strategy of P3⊗Pn and |S|=r be the number of removing vertices from P3⊗Pn. There are two cases according to the number of elements in S.
Case
1. If 0≤r≤(n/2), then w((P3⊗Pn)/S)≤n+r and c((P3⊗Pn)/S)≥1. Thus we have
(43)w(P3⊗PnS)-|S|-c(P3⊗PnS)≤n-1.
Case
2. If (n/2)≤r≤3n, then w((P3⊗Pn)/S)≤n+(n/2)-((r-(n/2))=2n-r and c((P3⊗Pn)/S)≥1. Thus we have
(44)w(P3⊗PnS)-|S|-c(P3⊗PnS)≤2n-2r-1.
Let f(r)=2n-2r-1 since f′(r)<0 the function f(r) is a decreasing function so it takes its maximum value at
(45)r=(n2),f(n2)=n-1.
From (43) and (45) we get
(46)Nr(P3⊗Pn)≤n-1.
There exist S* such that |S*|=(n/2), w((P3⊗Pn)/S)=n+(n/2) and c((P3⊗Pn)/S)≥1 thus we have
(47)Nr(P3⊗Pn)≥n-1.
From (46) and (47) we get Nr(P3⊗Pn)=n-1.The following theorem’s proof is very similar to that of Theorem24.Theorem 25.
LetP3⊗Pn be a tensor product of P3 and Pn and n≠0(mod4). Then
(48)Nr(P3⊗Pn)=2n-2⌈(n+1)2⌉-1.Theorem 26.
Let the tensor product ofKm and Kn is Km⊗Kn. Then
(49)Nr(Km⊗Kn)=Nr(Km-1,n-1)-1=max{m-5,n-5}.Proof.
Let(a,b) be any vertex of Km⊗Kn such that a∈Km and b∈Kn. The only vertices that are not adjacent to (a,b) in (Km⊗Kn) are (a,cj) with (j=1,2,…,n) and (di,b) with (i=1,2,…,m), where cj∈V(Kn) and di∈V(Km).
The vertices(a,cj) are not adjacent to each other, neither do the vertices (di,b). But these are adjacent to each other, so
(50)(Km⊗Kn){a,b}≅Km-1,n-1,Nr(Km⊗Kn)=Nr(Km-1,n-1)-1=max{m-4,n-4}-1=max{m-5,n-5}.Definition 27 (see [10]).
The composition of simple graphsG and H is the simple graph G[H] with vertex set V(G)×V(H), in which (u,v) is adjacent (u′,v′) if and only if either uu′∈E(G) or u=u′ and vv′∈E(H).Theorem 28.
LetP3[Pn] be the composition of P3 and Pn with n≥5. Then neighbor rupture degree of P3[Pn] is
(51)Nr(P3[Pn])={1,n≡1(mod4),0,n≡0,2,3(mod4).Proof.
Let the vertex set ofP3[Pn] be labeled as Pni, Pnii, and Pniii.
(52)
It can be easily seen thatP3[Pn] is the sequential join of three disjoint path graphs, P3[Pn]≅Pn+Pn+Pn. Then, according to the Theorem 10 we get
(53)Nr(P3[Pn])=Nr(Pn+Pn+Pn)=max{Nr(Pn∪Pn),Nr(Pn)}.
By Theorem 2, we have
(54)Nr(Pn)={0,n≡1(mod4),-1,n≡0,2,3(mod4).
To conclude the proof we need to findNr(Pn∪Pn). Let S be a subversion strategy of Pn∪Pn. Since Pn∪Pn has two identical disjoint path graphs, let x denote the number of removing vertices of each Pn and let |S|=2x.
Case
1. If x≤⌊(n-1)/4⌋,w((Pn∪Pn)∖S)≤2x+2 and c((Pn∪Pn)∖S)≥⌈(2n-6x)/(2x+2)⌉=⌈(n-3x)/(x+1)⌉, then we get
(55)w((Pn∪Pn)∖S)-|S|-c((Pn∪Pn)∖S)≤2-⌈n-3xx+1⌉.
Let f(x)=2-(n-3x)/(x+1), since f(x) is an increasing function it takes its maximum value at x=⌊(n-1)/4⌋. f(⌊(n-1)/4⌋)=5-(n+3)/(⌊(n-1)/4⌋+1). Since neighbor rupture degree has to be an integer, we have Nr(Pn∪Pn)≤⌈5-(n+3)/(⌊(n-1)/4⌋+1)⌉ and we get
(56)Nr(Pn∪Pn)≤{1,n≡1(mod4),0,n≡0,2,3(mod4).
Case
2. If x≥⌊(n-1)/4⌋, w((Pn∪Pn)∖S)≤2x, and c((Pn∪Pn)∖S)≥1, thus we get
(57)Nr(Pn∪Pn)≤-1.
From (56) and (57) we have
(58)Nr(Pn∪Pn)≤{1,n≡1(mod4),0,n≡0,2,3(mod4).
There exist S* such that |S*|=2⌊(n-1)/4⌋, w((Pn∪Pn)∖S)=(2⌊(n-1)/4⌋+1) and c((Pn∪Pn)∖S)=2 for n≡0,2,3(mod4), c((Pn∪Pn)∖S)=1 for n≡1(mod4).
Thus we have(59)Nr(Pn∪Pn)≥{1,n≡1(mod4),0,n≡0,2,3(mod4).
From (58) and (59) we get
(60)Nr(Pn∪Pn)={1,n≡1(mod4),0,n≡0,2,3(mod4).
By (54) and (60) we conclude the proof.Theorem 29.
Neighbor rupture degree of composition ofKm and any graph G is
(61)Nr(Km[G])=Nr(G).Proof.
Let the vertex set ofKm[G] be labeled as, Gi,Gii,…,Gm,
(62)
Let S be a subversion strategy of Km[G]. We have two cases according to the elements of S.
Case
1. Let we choose one element from any vertex set Gi(i=1,2,…,m); if u∈V(Gi) and S={u}, then it removes all of other vertex sets. So it depends on only Gi which we choose one element. Then we have
(63)Nr(Km[G])=Nr(Gi)=Nr(G).
Case
2. Let we choose two elements from any vertex set Gi(i=1,2,…,m) and Gj(j=1,2,…,m) with i≠j. Then (Km[G])/S is empty set. It contradicts to the definition of neighbor rupture degree. Thus we obtain
(64)Nr(Km[G])=Nr(G).Definition 30 (see [11]).
Annth power of a graph G is formed by adding an edge between all pairs of vertices of G with distance at most n. If n=2 then it is called a second power of a graph also called a square.Theorem 31.
Neighbor rupture degree ofPn2(n>6) is
(65)Nr(Pn2)={0,n≡1(mod6),-1,otherwise.Proof.
LetS be a subversion strategy of Pn2 and let |S|=r. There are two cases according to the number of elements of S.
Case
1. If 0≤r≤⌈n/6⌉-1, then w(Pn2/S)≤r+1, c(Pn2/S)≥(n-5r)/(r+1); then we get
(66)w(Pn2S)-|S|-c(Pn2∖S)≤r+1-r-n-5rr+1=6-n+5r+1.
Let
(67)f(r)=6-n+5r+1={0,n≡1(mod6),<0,otherwise.
Case
2. If =⌈n/6⌉, then w(Pn2/S)≤r,c(Pn2/S)≥1; then we get
(68)w(Pn2S)-|S|-c(Pn2S)≤r-r-1=-1thereforeNr≤-1.
Case
3. If ⌈n/6⌉+1≤r≤n, then w(Pn2/S)≤r-1, c(Pn2/S)≥1; then we get
(69)w(Pn2S)-|S|-c(Pn2∖S)≤r-1-r-1=-2thereforeNr≤-2.
According to (67), (68), and (69) we have
(70)Nr(Pn2)≤{0,n≡1(mod6),-1,otherwise.
There exist S* such that |S*|=⌈(n-1)/6⌉, w(Pn2/S*)=⌈n/6⌉, c(Pn2/S*)=1; then
(71)w(Pn2S*)-|S*|-c(Pn2S*)={0,n≡1(mod6),1,otherwise.
By (70) and (71) we get the result,
(72)Nr(Pn2S)=max{w(Pn2S)-|S|-c(Pn2S)}={0,n≡1(mod6),1,otherwise.


## 4. Conclusion

In this study, we investigate the neighbor rupture degree of graphs obtained by graph operations. The graph operations are used to obtain new graphs. Union, join, complement, composition, power, cartesian product, and tensor product are taken into consideration in this work. These operations are performed to various graphs and their neighbor rupture degrees were determined.



---

*Source: 836395-2013-07-17.xml*