# Bondage Numbers ofC4 Bundles over a Cycle Cn

Authors: Moo Young Sohn; Fu-Tao Hu; Jaeun Lee
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Graph bundles generalize the notion of covering graphs and graph products. Graph bundles have been applied in computer architecture and communication networks. The bondage number is an important parameter for measuring the vulnerability and stability of the network domination under link failure. The bondage numberb(G) of a graph
G is the minimum number of edges whose removal enlarges the domination number. In this paper, we show that the bondage number of every C4 bundles over a cycle Cn(n≥4)
is equal to 4.


---

## Body

## 1. Introduction

For notation and graph theoretical terminology not defined here, we follow [1]. Specifically, let G=(V,E) be an undirected graph without loops and multiedges, where V=V(G) is the vertex set and E=E(G) is the edge set, which is a subset of the set of all unordered pair of V. A graph G is nonempty if E(G)≠∅. Two vertices x and y are adjacent if {x,y}∈E(G). We will denote an edge {x,y} by xy if it does not make any confusion. For any disjoint subset S,T⊆V, we denote [S,T] by the edge set between S and T of G. For any subset S of V, let 〈S〉 be the subgraph induced by S. Throughout this paper, we use Pn and Cn to denote a path and a cycle of order n, respectively. A subset D⊆V(G) is called a dominating set of G if every vertex not in D has at least one neighbor in D. The domination number of G, denoted by γ(G), is the minimum cardinality among all dominating sets.The domination is very important and classic conception that it has become one of the most widely studied topics in graph theory and also is frequently used to study properties of interconnection networks. The early results on this subject have been, in detail, surveyed in the two excellent books written by Haynes et al. [2, 3]. In the recent decade, a large number of research papers on domination as well as related topics appear in many scientific journals because of their applications in many fields such as networks, and wireless communication.In 1990, Fink et al. [4] introduced the bondage number as a parameter for measuring the vulnerability of the interconnection network under link failure. The minimum dominating set of sites plays an important role in the network because it dominates the whole network with the minimum cost. So we must consider whether its function remains good under attack. Suppose that someone such as a saboteur does not know which sites in the network take part in the dominating role but does know that the set of these special sites corresponds to a minimum dominating set in the related graph. Then how many links does he have to attack so that the cost can not remain the same in order to dominate the whole network? That minimum number of links is just the bondage number.A subsetB of E(G) is called a bondage set of G if its removal from G results in a graph with larger domination number than γ(G). The bondage numberb(G) of a nonempty graph G is the minimum number of edges in a bondage set of G. Since the domination number of every spanning subgraph of a nonempty graph G is at least as great as γ(G), the bondage number of a nonempty graph is well defined. Many results on this topic are obtained in the literature. Fink et al. [4] computed the exact value of the bondage number for only a few classes of graphs, such as complete graphs, paths, cycles, and complete t-partition graphs. In 2012, Hu and Xu [5] have showed that the problem of determining bondage number for general graphs is NP hard. Recently, Xu [6] gave a review on bondage numbers in 2013.For the Cartesian productG1□G2 of two graphs G1 and G2, Hu and Xu [7] determined b(Pn□Pm) for m≤4, Dunbar et al. [8] determined b(Cn□P2) for n⩾3, Sohn et al. [9] determined b(Cn□C3) for n⩾4, Kang et al. [10] determined b(Cn□C4) for n⩾4, Huang and Xu [11] determined b(C5i□C5j) for any positive integers i and j, and Xiang et al. [12] determined b(Cn□C5) for n⩾5 and n≢3(mod5). Sohn and Cao [13] determined bondage number of the graph bundle Cn□φC5 having reflection voltage assignment.LetB and F be graphs. A graph G is a Cartesian graph bundle with fibre F over the base graph B if there is a graph map p:G→B such that for each vertex v∈V(B), p-1(v)≃F, and for each edge e∈E(B), p-1(e)≃K2□F. The triple (G,p,B) is called a presentation of G as a Cartesian graph bundle. We can also understand the Cartesian graph bundle as a graph, which is obtained from the base graph by replacing each of its vertices with a copy of the fibre graph and each of its edges by matching between the copies of the fibre, corresponding to the endpoints of the edge. The edges of the matching define an isomorphism between the copies of the fibre. For the completeness, let B→ be the digraph obtained from B by replacing each edge of B with a pair of oppositely directed edges. The set of directed edges of B→ is denoted by E(B→). By e-1, we mean the reverse edge to an edge e∈E(B→). We denote the directed edge e of B→ by uv→ if the initial and terminal vertices of e are u and v, respectively. For a finite group Γ, a Γ-voltage assignment of G is a function φ:E(B→)→Γ such that φ(e-1)=ϕ(e)-1 for all e∈E(B→). We denote the set of all Γ-voltage assignments of B by C1(B;Γ). Let Aut(F) be the set of all automorphisms of F and let φ∈C1(B;Aut(F)). The bundle G is determined by F, B and φ is the graph B□φF with the vertex set V(B□ϕF)=V(B)□V(F), and two vertices (u1,v1) and (u2,v2) are adjacent in B□ϕF if either u1u2→∈E(B→) and v2=v1ϕ(u1u2) or u1=u2 and v1v2∈E(F).It is well known [14, 15] and easy to see that for any spanning tree T of B, there is a ψ:E(B→)→Aut(F) such that ψ(e)=identity for e∈E(T→) and G=B□φF≃B□ψF. From the definition, it follows that Cartesian graph bundles over paths and trees are exactly Cartesian product graphs and that we can represent Cartesian graph bundles over a cycle with a set of isomorphisms over the edges of the cycle, with at most one nonidentical isomorphism (if all isomorphisms are identities, the bundle is the Cartesian product of two graphs B and F).The domination numbers of the Cartesian product of two graphs have been given great attention in domination theory. The most interesting problem is Vizing’s conjecture [16]: For every pair of finite graphs G and H, γ(G□H)≥γ(G)γ(H). Vizing’s conjecture is arguably the main open problem in the area of domination theory. There are many related articles about Vizing conjecture and see the recent survey [17]. There are many variants about Vizing’s conjecture with different dominations and product. The domination number of the graph bundle is an interesting problem. But the conjecture on graph bundle corresponding to Vizing’s conjecture on the Cartesian product of two graphs is not true [18].In this paper, we compute the bondage number of the graph bundleCn□φC4 (n≥4) as follows.Main Theorem.For anyn≥4andφ∈C1(Cn;Aut(C4)), b(Cn□φC4)=4.


## 2. Preliminary Results

Throughout this paper, we assume that a pathPn and a cycle Cn both have the vertex set {1,2,…,n}. Use Gn to denote the Cartesian graph bundle product Cn□φC4 of two cycles Cn and C4. Use Hn to denote the Cartesian product Pn□C4 of two paths Pn and C4. Let both Gn and Hn have vertex set {uij∣1≤i≤n,1≤j≤4}. Clearly, for any Cartesian graph bundle, Pn□φC4 is isomorphic to Hn. For a bundle Cn□φC4, we define ψ:E(B→)→Aut(C4) by ψ(e)= identity for e≠(n-1)n→ or e≠n(n-1)→ and ϕ(n-1n)→=φ(12→)φ(23→)⋯φ((n-1)n→)φ(n1→). Then Cn□φC4 and Cn□ϕC4 are isomorphic (see Figure 1). In the rest of the paper, we will denote Cartesian graph bundle over cycle Cn by Cn□φF, where φ(e)={identity} for e≠(n-1)n→ or e≠n(n-1)→.Figure 1
Size representation of Cartesian graph bundles over cycleC4.In the following we always use this representation to representGn for simplicity. For given Gn and Hn, the ith column of them is the vertex set Xi={ui1,ui2,ui3,ui4} for 1≤j≤n and an element in it is said to be vertical and the jth raw Yj={u1j,u2j,…,unj} for 1≤j≤4 and an element in it is said to be horizontal.LetGn-Hi and Hn-Hi be the subgraph of Gn and Hn induced by {ukj∣i+1≤k≤n,1≤j≤4} for each i=1,2,…,n-1, respectively. Clearly, Gn-Hi≅Hn-Hi≅Hn-i. In this paper, when we write a vertex ui(j+1) for 1≤j≤4 and if j=4, then ui(j+1) means ui1. We state some useful results on γ(Gn) and γ(Hn), which will be used in our proofs.Lemma 1 (see [19]).
Considerγ(Cn□C4)=n, n≥2.Lemma 2 (see [18]).
Considerγ(Gn)=n, n≥2.Lemma 3 (see [10]).
Considerγ(Hn)=n, n≥2.Lemma 4 (see [10]).
Ife1,e2∈E(Hn), n≥2 are adjacent that is, they have a common end-vertex, then γ(Hn-{e1,e2})=n.Lemma 5 (see [10]).
Ife1 is a horizontal edge and e2 is a vertical edge of Hn for n≥2, then γ(Hn-{e1,e2})=n.Lemma 6.
LetD be a dominating set of Hn. Then |D∩V(Hn-Hi)|≥γ(Hn-Hi+1) and |D∩V(Hi+1)|≥γ(Hi) for each i=0,1,…,n-1, and n≥2.Proof.
We only need to prove that|D∩V(Hi+1)|≥γ(Hi) since Hn-Hi≅Hn-i. Let D′=D∩V(Hi+1).
IfD′∩Xi+1=∅, then D′ is a dominating set of Hi, and hence |D∩V(Hi+1)|≥γ(Hi).
AssumeD′∩Xi+1≠∅. Let Bi={j∣u(i+1)j∈D′}. Then D′′=(D′∖Xi+1)∪{uij∣j∈Bi} is a dominating set of Hi and |D′′|⩽|D′|. Thus, we have |D∩V(Hi+1)|≥|D′′|≥γ(Hi).Lemma 7.
LetD be a minimum dominating set of Hn. Then |X1∩D|=1 and |Xn∩D|=1 for n≥2.Proof.
By Lemma3, |D|=n. By the symmetry of Hn, we only need to prove |X1∩D|=1. It is easy to see that the conclusion is true for n=2,3. Assume now n≥4. By contradiction.
Assume|X1∩D|=0 and then |X2∩D|=4. By Lemmas 3 and 6, |D∩V(Hn-H2)|≥γ(Hn-H3)≥n-3. Thus |D|=|X2∩D|+|D∩V(Hn-H2)|≥n+1, a contradiction with |D|=n. So |X1∩D|≥1.
Assume now|X1∩D|≥3. By Lemmas 3 and 6, |D∩V(Hn-H1)|≥γ(Hn-H2)=n-2. Thus |D|=|X1∩D|+|D∩V(Hn-H1)|≥n+1, a contradiction with |D|=n. So |X1∩D|≤2.
Finally, assume|X1∩D|=2.
IfX2∩D=∅, then D′=D∖X1 is a dominating set of Hn-H2 and |X3∩D′|⩾2. By the induction hypothesis, D′ is not a minimum dominating set of Hn-H2, and hence |D′|⩾γ(Hn-H2)+1=n-1 by Lemma 3. Then |D|=2+|D′|⩾n+1, a contradiction with |D|=n.
IfX2∩D≠∅, there exists a vertex u2j such that D′′=(D∖X1)∪{u2j} is a dominating set of Hn-H1 and |X2∩D′′|⩾2. By the induction hypothesis, D′′ is not a minimum dominating set of Hn-H1, and hence |D′′|⩾γ(Hn-H1)+1=n by Lemma 3. Then |D|⩾|X1∩D|+|D′′|-1⩾n+1, a contradiction with |D|=n. The lemma follows.Lemma 8.
If bothe1 and e2 are horizontal edges of Hn for n≥3, then γ(Hn-{e1,e2})=n.Proof.
Without loss of generality, assumee1=ui1u(i+1)1 for some integer i with 1≤i≤⌊n/2⌋. Let
(1)D={{uk2∣kisodd}∪{uℓ4∣ℓiseven}2222222222ife2∈E(〈Y1∪Y3〉);{uk1∣kisodd}∪{uℓ3∣ℓiseven}2222222222ife2∈E(〈Y2∪Y4〉).
Then D is a dominating set of Hn-{e1,e2} and |D|=n.Lemma 9.
Lete1=uijui(j+1) and e2=ukj′uk(j′+1)(i≤k) be any two vertical edges of Hn for n≥4 and let e1 and e2 be adjacent for i=k=1 or i=k=n. Then, one has γ(Hn-{e1,e2})=n.Proof.
Ife1 and e2 are adjacent, then the conclusion is true by Lemma 4. Next, assume e1 and e2 are nonadjacent. This imply that |j′-j|=2 when i=k.
Assume1<i<k<n. We consider Hi and Hn-Hi. By Lemma 4, γ(Hi-e1)=i and γ(Hn-Hi-e2)=n-i and hence γ(Hn-{e1,e2})=n.
Assume1<i=k<n. Without loss of generality, suppose j=1, j′=3 and i=k≤⌈n/2⌉≤n-2. Let D1={up3∣pisodd}∪{uq1|qiseven} where 1≤p, q≤i and D2={up2∣pisodd}∪{uq4|qiseven} where i<p, q≤n. Then D=D1∪D2 is a dominating set of Hn-{e1,e2} and |D|=n.
Assume nowi=1 or k=n. Without loss of generality, suppose i=1.
Ifk=1, then by the assumption, e1 and e2 are adjacent. By Lemma 4, γ(Hn-{e1,e2})=n.
Ifk=2, then without loss of generality, suppose j=1. Let
(2)D={{u13}∪{u21}∪{up2∣pisodd,p≥3}22.22∪{uq4∣qiseven,q≥3},222222222222222.2222ifj′=1;{up3∣pisodd}∪{uq1∣qiseven},2222222222222222222ifj′=2or3;{up4∣pisodd,p≥3}∪{uq2∣qiseven,q≥3},2222222222222222222222222222222222ifj′=4.
Then D is a dominating set of Hn-{e1,e2} and |D|=n.
Ifk>2, then we consider H2 and Hn-H2. By Lemma 4, γ(H2-e1)=i+1 and γ(Hn-H2-e2)=n-i-1 and hence γ(Hn-{e1,e2})=n.Proposition 10.
Letx be a vertex that belongs to X1 or Xn. Then there exists a minimum dominating set D of Hn such that x∈D for n≥2.


## 3. Main Results

Theorem 11.
b
(
H
n
)
=
2 for n≥2.Proof.
For any edgee∈E(Hn), by Lemmas 3 and 4, γ(Hn-{e})=n=γ(Hn). Thus b(Hn)≥2. Next, we prove b(Hn)≤2.
Lete1=u11u12 and e2=u13u14. Let D be a minimum dominating set of Hn-{e1,e2}. We only need to prove |D|>γ(Hn)=n. It is easy to verify that |D|=3>γ(Hn) for n=2. Next assume n≥3.
Notice thatD is also a dominating set of Hn. If |D∩X1|≠1, then by Lemma 7, D is not a minimum dominating set of Hn and hence |D|>γ(Hn). Now assume |D∩X1|=1. Then |D∩X2|≥2. Notice that D′=D∖X1 is a dominating set of Hn-H1≅Hn-1. By Lemma 7, D′ is not a minimum dominating set of Hn-H1; hence, |D′|>γ(Hn-H1)=n-1, and hence, |D|=|D′|+1>n.Lemma 12.
Considerb(Gn)≤4 for n≥4.Proof.
LetD be a minimum dominating set of Gn-u14. Then γ(Gn-EGn(u14))=|{u14}|+γ(Gn-u14)=1+|D| where EGn(u14) is all the edges incidents with u14. Therefore, we only need to prove |D|≥γ(Gn)=n. If one of {u11,u13,u24,un4} belongs to D, then D is also a dominating set of Gn. By Lemma 2, |D|≥γ(Gn)=n. Assume {u11,u13,u24,un4}∩D=∅ in the following.
IfX1∩D=∅, then D is also a dominating set of Gn-H1≅Hn-1, |X2∩D|≥2 or |Xn∩D|≥2. By Lemma 7, D is not a minimum dominating set of Gn-H1, and hence |D|≥γ(Hn-1)+1=n.
Assume nowX1∩D≠∅. Then X1∩D={u12} since {u11,u13,u24,un4}∩D=∅. If |(X2∪Xn)∩D|≥2, then there exists a vertex x∈X2∪Xn such that D′=(D∖{u12})∪{x} is a dominating set of Gn-H1≅Hn-1, and |X2∩D′|≥2 or |Xn∩D′|≥2. By Lemma 7, D′ is not a minimum dominating set of Gn-H1 and hence |D|≥|D′|≥γ(Hn-1)+1=n.
If|(X2∪Xn)∩D|≤1, then X2∩D=∅ or Xn∩D=∅. Without loss of generality, assume X2∩D=∅. So {u31,u33,u34}⊆D. Let D′′=(D∖{u31,u33,u34})∪{u24,u32,u44}. Then D′′ is a dominating set of Gn, and hence |D|≥|D′′|≥γ(Gn)=n.Lemma 13.
Considerb(Gn)≥4 for n≥4.Proof.
It suffices to show thatγ(Gn-{e1,e2,e3})=n for any three edges e1,e2,e3∈E(Gn).
Note.Since n≥4, by the isomorphism of Gn, we can assume that none of these three edges is in [Xn-1,Xn]. That is, ei is either horizontal or vertical for each i=1,2,3.
According to the number of horizontal and vertical edges, it divides into two cases.
Case
1. At least one of e1, e2, and e3 is horizontal. Without loss of generality, assume e1=u11un1.
Assume at least one ofe2 and e3 is horizontal, or both e2 and e3 are vertical and they satisfy the condition in Lemma 9. It is easy to see that Gn-[X1,Xn]≅Hn. By Lemmas 5, 8, and 9,  γ(Gn-[X1,Xn]-{e2,e3})=n. Thus γ(Gn-{e1,e2,e3})≤γ(Gn-[X1,Xn]-{e2,e3})=n.
The remaining case is thate2 and e3 do not satisfy the condition in Lemma 9. Without loss of generality, assume e2=u11u12. Then e3=u13u14.
By Proposition10, let D′ be a minimum dominating set of Gn-H2≅Hn-2 that contains un4. Let D={u13,u21}∪D′. Then D is a dominating set of Gn-{e1,e2,e3} with cardinality n.
Case
2. All of e1, e2, and e3 are vertical. Without loss of generality, assume e1=u11u12. Let e2=ukjuk(j+1), e3=ulj′ul(j′+1) and k≤ℓ.
Ifk=ℓ=1, then without loss of generality, assume j=2 and j′=3. By Proposition 10, let D′ be a minimum dominating set of Gn-H2≅Hn-2 such that un2∈D′. Then D′∪{u11,u23} is a dominating set of Gn-{e1,e2,e3} with cardinality n.
Assumek=ℓ>1 or 1=k<ℓ. Without loss of generality, suppose k=ℓ>1. If k≥3 or k=2 and |j-j′|≠2 (see Figure 2), then e2 and e3 are adjacent. We consider Hn-1-H1≅Hn-2 and 〈X1∪Xn〉≅H2. By Lemma 4, γ(Hn-1-H1-{e2,e3})=n-2 and γ(〈X1∪Xn〉-{e1})=2. Thus γ(Gn-{e1,e2,e3})≤n. If k=2 and |j-j′|=2, then e2 and e3 are nonadjacent. Without loss of generality, assume j=1 and j′=3. By Proposition 10, let D′′ be a minimum dominating set of Gn-H2≅Hn-2 such that u32∈D′′. Then D′′∪{u13,u21} is a dominating set of Gn-{e1,e2,e3} with cardinality n.
Assume now1<k<ℓ. We consider Hn-1-H1 and 〈X1∪Xn〉≅H2. By Lemmas 4 and 9, γ(〈X1∪Xn〉-{e1})=2 and γ(Hn-1-H1-{e1,e2})=n-2. Therefore, γ(Gn-{e1,e2,e3})≤γ(〈X1∪Xn〉-{e1})+γ(Hn-1-H1-{e1,e2})=n.Figure 2
Dominating sets (bold vertices) ofG9-{e1,e2,e3} in Case 2 of Lemma 13.From Lemmas12 and 13, we have the main theorem.Theorem 14.
For anyn≥4 and φ∈C1(Cn;Aut (C4)), b(Cn□φC4)=4.Since Cartesian product graphCn□C4 is the bundle graph Cn□φC4 corresponding to the φ such that φ(e)= identity for each edge e∈E(C→n), we have the following.Corollary 15 (see [10]).
For anyn≥4, b(Cn□C4)=4.



---

*Source: 520251-2013-12-11.xml*