# The Bondage Number of Generalized Petersen GraphsPn,2

Authors: Lidan Pei; Xiangfeng Pan
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The domination numberγG of a nonempty graph G is the minimum cardinality among all subsets D⊆VG such that NGD=VG. The bondage number bG of a graph G is the smallest number of edges whose removal from G results in a graph with larger domination number. The exact value of bPn,2 for n=0,3,4mod5 and the bounds of bPn,2 for n=1,2mod5 are determined.


---

## Body

## 1. Introduction

For terminology and notation on graph theory not given here, we refer the reader to [1]. Let G=V,E be a finite, undirected graph without loops, multiple edges, and isolated vertices, where V=VG is the vertex set and E=EG is the edge set. A graph G is nonempty if EG≠∅. For a vertex v, let NGv=u:uv∈EG be the open neighborhood and NGv=Nv∪v be the closed neighborhood. For a set D⊆VG, the open neighborhood NGD is defined to be ∪u∈DNGu and the closed neighborhood is NGD=NGD∪D. We use GD to denote the subgraph of G induced by D.A subsetD⊆VG is a dominating set of G if NGD=VG. The domination number γG is the minimum cardinality of a dominating set of G. A dominating set is called a γ-set if its cardinality is γG. Studies on domination number have long attracted graph theorists for their applications and theoretical interest. The two outstanding domination books by Haynes et al. [2, 3] have a comprehensive research of domination.The bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number greater than the domination number of G. That is,(1)bG=minB:B⊆EG,γG−B>γG.The bondage number of a nonempty graph is well defined since the domination number of every spanning subgraph of a nonempty graphG is at least as great as γG. The bondage number is proposed by Fink et al. [4] in 1990. However, it is quite difficult to compute the exact value of the bondage number for general graphs. Hu and Xu [5] showed that the problem of determining bondage number for arbitrarily given graph is NP-hard. Therefore, it is important to determine bondage numbers for some graphs or networks with simple structure. The exact value of the bondage number has been worked out for only a few classes of graphs, such as complete graphs, paths, cycles, complete t-partite graphs [4], trees [6–8], complete t-partite digraphs [9], de Bruijn and Kautz digraphs [10], the Cartesian product of two cycles [11–13], the Cartesian product of two paths [14], the strong product of two paths [15], and Mycielski Graphs [16]. For a further study on the advances of bondage number, the readers are suggested to refer to [17, 18].For positive integer numbersn and k, where n>2k, the generalized Petersen graph Pn,k is a graph on 2nn≥3 vertices with(2)VPn,k=vi,ui:0≤i≤n−1;EPn,k=vivi+1,viui,uiui+k:0≤i≤n−1,subscripts modulon.Although the generalized Petersen graphPn,k has a special construction, the complexity and difficulty are ubiquitous throughout the study on it for each k≥1. Even so, many researchers still insist on Pn,k and obtain many graph parameter values other than the bondage number of Pn,k [19–25]. Yet, the studies on the domination number and its variations of Pn,k are attractive. Recall that the problems of determining the domination number and bondage number for arbitrarily given graph are NP-complete [26] and NP-hard, respectively. Therefore, researchers tend to study the domination problem of generalized Petersen graph Pn,k with a given small value for k or a given relationship between n and k [27–33]. It is worth mentioning that Fu et al. [28] showed the exact domination number of generalized Petersen graph Pn,2. Hence, it is meaningful to study the bondage number of generalized Petersen graph Pn,2 in this paper. The rest of the paper is organized as follows. Section 2 shows the lower bound of bPn,2. In Section 3, we present the upper bounds of bPn,2 for n=0,3,4mod5 and n=1,2mod5, respectively. In particular, the upper bound of bPn,2 for n=0,3,4mod5 is just the exact value.


## 2. Lower Bound on Bondage Number ofPn,2

Letn=5m+t, that is, t≡nmod5 and m=⌊n/5⌋. Fu et al. [28] proved that γPn,2=n−⌊n/5⌋−⌊n+2/5⌋ and showed a minimum dominating set D of graph Pn,2, where(3)D=v5i+1,u5i+2,v5i+3:0≤i≤m−1,ift=0,v5i+1,u5i+2,v5i+3:0≤i≤m−1∪vn−1,ift=1,v5i+1,u5i+2,v5i+3:0≤i≤m−1∪vn−2,un−1,ift=2,v5i+1,u5i+2,v5i+3:0≤i≤m−1∪vn−2,un−3,ift=3,v5i+1,u5i+2,v5i+3:0≤i≤m−1∪vn−3,un−2,vn−1,ifPn,2t=4.In order to determine the lower bound on bondage number ofPn,2, we need to first prove the following lemma by the definition of bondage number.Lemma 1.
γ
P
n
,
2
−
e
1
,
e
2
≤
γ
P
n
,
2, where e1 and e2 are any two edges of G.Proof.
By the definition of graphPn,2, we need to consider the following six cases: e1=vivi+1, e2=vjvj+1; e1=viui, e2=vjuj; e1=uiui+2, e2=ujuj+2; e1=vivi+1, e2=vjuj; e1=vivi+1, e2=ujuj+2; e1=viui, e2=ujuj+2, 0≤i,j≤n−1. Actually, we only show the proof for e1=vivi+1, e2=vjvj+1 and e1=viui, e2=vjuj, since the proofs for the other four cases are similar (for reference, see Appendix).
Assume thatD is the minimum dominating set of graph Pn,2 constructed in [28]. We prove γPn,2−vivi+1,vjvj+1≤γPn,2 for 0≤i,j≤n−1 in the following. Without loss of generality, we assume that i<j and j=i+k, where 1≤k≤n. If ⌊n/2⌋+1≤k≤n, then Pn,2−vivi+1,vjvj+1≅Pn,2−vivi+1,vn−jvn−j+1. In view of γPn,2−vivi+1,vjvj+1=γPn,2−vivi+1,vn−jvn−j+1 and n−j−i≤⌊n/2⌋, we only need to prove γPn,2−vivi+1,vjvj+1≤γPn,2 for 1≤k≤⌊n/2⌋. Let(4)E0=v5i+1v5i+2,v5i+2v5i+3,v5i+4v5i+50≤i≤m−1,E1=E0∪vn−1v0,E2=E0∪vn−2vn−1,vn−1v0,E3=E0∪vn−3vn−2,vn−1v0,E4=E0∪vn−3vn−2,vn−2vn−1,vn−1v0.
We claim that for eachk∈1,2,…,⌊n/2⌋, there exists an i0∈0,1,…,n−1 such that vi0vi0+1,vj0vj0+1∈Et where j0=i0+k. We consider t=0,1,2,3,4, respectively.
Fort=0, if k=0,1,3 (mod 5), let i0=1; then, j0=i0+k=1,2,4 (mod 5) such that vi0vi0+1,vj0vj0+1∈E0. If k=2,4 (mod 5), let i0=2; then, j0=4,1 (mod 5) such that vi0vi0+1,vj0vj0+1∈E0.
Fort=1, if k=1,3,4 (mod 5), let i0=n−1−k. Then, i0=n−1−k,ifk=0,2,4mod5,n−2−k,ifk=1,3mod5. and i0=4,2,1 (mod 5) such that vi0vi0+1,vj0vj0+1∈E1. If k=0,2 (mod 5), let i0=n−2−k. Then, j0=n−2=4 (mod 5) and i0=4,2 (mod 5) such that vi0vi0+1,vj0vj0+1∈E1.
Fort=2, let i0=n−1−k when k=0,2,4 (mod 5); then, i0=1,4,2 (mod 5) and j0=n−1 such that vi0vi0+1,vj0vj0+1∈E2. Let i0=n−2−k when k=1,3 (mod 5); then, i0=4,2 (mod 5) and j0=n−2 such that vi0vi0+1,vj0vj0+1∈E2.
Fort=3, let i0=n−1−k when k=0,3 (mod 5), i0=n−3−k when k=1,4 (mod 5), and i0=n−4−k when k=2 (mod 5). Thus, vi0vi0+1,vj0vj0+1∈E3.
Fort=4, let i0=n−1−k if k=1,2,4 (mod 5) and i0=n−2−k if k=0,3 (mod 5). Then, vi0vi0+1,vj0vj0+1∈E4.
It is easy to verify thatD is a dominating set of graph Pn,2−Et for t=0,1,2,3,4. Hence, D is a dominating set of graph Pn,2−vi0vi0+1,vj0vj0+1. In consideration of Pn,2−vi0vi0+1,vj0vj0+1≅Pn,2−vivi+1,vjvj+1, we get that γPn,2−vivi+1,vjvj+1=γPn,2−vi0vi0+1,vj0vj0+1≤γPn,2 for any 0≤i<j≤n−1, j=i+k and k∈1,2,…,⌊n/2⌋. The result follows.
Next, we proveγPn,2−viui,vjuj≤γPn,2 for 0≤i,j≤n−1. Let j=i+k, k∈1,2,…,⌊n/2⌋. We claim that D is a dominating set of Pn,2−Et for t=0,1,2,3,4, where(5)E0=v5i+2u5i+2,v5i+4u5i+4,v5i+5u5i+50≤i≤m−1,E1=E0\v5mu5m∪v0u0,E2=E0\v5mu5m∪vn−1un−1,v0u0,E3=E0∪vn−1un−1,v0u0,E4=E0∪vn−2un−2,v0u0.
Fort=0, let(6)i0=n−k,ifk=0,1,3mod5,n−1−k,ifk=2,4mod5.
Fort=1 and n=6, D′=u0,u1,v0,v3 is a γ-set of P6,2, and it is a dominating set of Pn,2−viui0≤i≤5. Thus, γP6,2−viui,vjuj≤D′=γP6,2. For t=1 and n>6, let(7)i0=4,ifk=1,n−k,ifk=1,2,4mod5k≠1,n−2−k,ifk=0mod5,n−4−k,ifk=3mod5.
Fort=2, let(8)i0=4,ifk=1,n−k,ifk=0,3mod5,n−1−k,ifk=1,2,4mod5k≠1.
Fort=3, let(9)i0=n−k,ifk=1,3,4mod5,n−1−k,ifk=0,2,mod5.
Fort=4, let(10)i0=n−k,ifk=0,2,4mod5,n−2−k,ifk=3mod5,n−4,ifk=1mod5.
The integersi0 and j0=i0+k are obtained such that vi0ui0,vj0uj0∈Et for t=0,1,2,3,4n≠6, respectively. Thus, D is a dominating set of graph G=Pn,2−vi0ui0,vj0uj0,n≠6. As a consequence, γPn,2−vivi+1,vjvj+1=γG≤γPn,2.
It is well known thatγPn,2−e1,e2≥γPn,2 for any two edges e1,e2. Combining Lemma 1, we obtain that γPn,2−e1,e2=γPn,2, which implies the following theorem.Theorem 1.
b
P
n
,
2
≥
3.


## 3. Upper Bound on Bondage Number ofPn,2

Letn=5m+t, where t≡nmod5 and m=⌊n/5⌋. The main results we get in this section are bPn,2≤3 for t=0,3,4 and bPn,2≤5 for t=1,2. We prove the above results mainly by mathematical induction on m in Lemma 3. As a recursive condition in mathematical induction, the inequation shown in Lemma 2 is important and necessary. In addition, due to the complexity inherent in the study of domination number and generalized Petersen graph, the proof for Lemma 2 is inevitably tedious and difficult. Let Gn=Pn,2−v2; we first present an algorithm which constructs from Gn a smaller graph Gn−5=Pn−5,2−v2.Figure1 gives an illustration for Algorithm 1.Figure 1
Algorithm1.Algorithm 1: The construction for graph G(n − 5) from graph G(n).
Input: the graphGn with VGn=VPn,2\v2, EGn=EPn,2\v1v2,v2v3,v2u2, n≥10.
Output: the graph G″.
Step 1. Delete the subset of vertices
v
i
,
u
i
5
≤
i
≤
9
, along with their 18 incident edges. Denote the resulting graph by
G
′
.
Step 2. Define the graph
G
″
to have vertex set
V
G
″
=
V
G
′
and edge set
E
G
″
=
E
G
′
∪
v
4
v
10
,
u
3
u
10
,
u
4
v
11
. Return
G
″
.Observation 1.
For eachn≥10, the graph G″ returned by Algorithm 1 is isomorphic to Gn−5=Pn−5,2−v2.Lemma 2.
For eachn≥10, γGn≥γGn−5+3.Proof.
We assume thatn≥10, and show γGn−5≤γGn−3. Let S be a γ-set of Gn and G′ and G″ be the graphs returned by Algorithm 1. Then, G″≅Gn−5. We will identify VGn−5 with VG″ and EGn−5=EG″. Then, VGn−5=VGn−T, where T=ui,vi5≤i≤9. Let S′=S∩VGn−5. Then, we get that S′=S−S∩T=γGn−S∩T and the set S′ can dominate all vertices in VGn−5, except possibly vertices in R=u3,u4,v4,v10,u10,u11. We consider the following cases.Case 1.
S
∩
T
≥
5.Sinceu4,u10 dominates the vertices in R and S′=S∩VG′ dominates the vertices in VGn−5∖R, we have that S′∪u4,u10 forms a dominating set of Gn−5. Hence, γGn−5≤S′∪u4,u10=S−S∩T+2≤γGn−3.Case 2.
S
∩
T
=
4. Then, S′=S−4=γGn−4.
The vertices inS∩T can dominate at most three vertices in R; otherwise, all the four vertices in S∩T belong to Q=v5,u5,u6,u8,u9,v9. Thus, v7 cannot be dominated by S since NGnv7∩Q=∅. Therefore, S∩Q≤3.Subcase 1.
S
∩
Q
=
0. Since S∩T=4, we get that S∩T=NGnv7. Thus, S−v7 is a dominating set of Gn, a contradiction with the minimality of S. Hence, this case does not exist.Subcase 2.
S
∩
Q
=
1. In this case, there is only one vertex x∈R dominated by S∩T; then, S′∪x is a dominating set of Gn−5. Thus, γGn−5≤S′∪x≤γGn−3.Subcase 3.
S
∩
Q
=
2.
Suppose thatx,y∈R are dominated by S∩T; thus, x and y may not dominated by S′. If z∈NGn−5x∩NGn−5y for some vertex z∈VGn−5, then S′∪z is a dominating set of Gn−5 and the result follows. If NGn−5x∩NGn−5y=∅, then there exist the following three possible cases (see Figure 2). To make the following proof easier to understand, we attach the corresponding graph for each case. Furthermore, in each figure a vertex colored dark indicates a vertex in S, a vertex ⊕ indicates a possible vertex in S, and a vertex ⊚ indicates a vertex not dominated by S∩Q and S′. Since S∩Q=2, the vertices ⊚ should be dominated by the two vertices in S∩T−Q=S∩NGnv7.(1)
S∩Q=u5,u6 (see Figure 2(a)), that is, u3,u4∈R are dominated by S∩T.It is obvious thatS′∪v3,v4 or S′∪v3,u4 is a dominating set of Gn−5 in this case. For dominating vertex v4 in graph Gn, at least one vertex in γ− belongs to S. Hence,(11)γGn−5≤S′∪v3,v4≤S′+1=γGn−3or(12)γGn−5≤S′∪v3,u4≤S′+1=γGn−3.(2)
S∩Q=u6,u8 (see Figure 2(b)), that is, u4,u10∈R are dominated by S∩T.In this case,S′∪v4,v10 can be a dominating set of Gn−5. If v4,v10∩S=∅, then S∩T=S∩Q∪v6,v8 for dominating vertices v5 and v9 in graph Gn. It implies that vertex u7 cannot be dominated by S=S′∪S∩T, a contradiction. Therefore, v4,v10∩S≠∅. It follows that(13)γGn−5≤S′∪v4,v10≤S′+1=γGn−3.(3)
S∩Q=u5,u9 (see Figure 2(c)), that is, u3,u11∈R are dominated by S∩T.
SinceNGnv4\v5∩S≠∅ and NGnv10\v9∩S≠∅, at least one vertex of v3,v4,u4 and v10,u10,v11 belongs to S. Since v3,u10∈NGn−5u3, S′∪u11 is a dominating set of Gn−5 if one vertex of v3,u10 belongs to S. Since u4,v11∈NGn−5u11, S′∪u3 is a dominating set of Gn−5 if one vertex of u4,v11 belongs to S. In the following, we just need to consider v4,v10⊆S. Then, S′v10∪v11,u10 is a dominating set of Gn−5. Hence,(14)γGn−5≤S′+1=γGn−3.Subcase 4.
S
∩
Q
=
3; then, S∩NGnv7=1 and there exist three vertices in R dominated by S∩T. Suppose that x,y,z∈R are dominated by S∩T. If x,y,z⊆NGn−5w where w∈VGn−5, then S′∪w is a dominating set of Gn−5, which means that(15)γGn−5≤S′∪w=γGn−S∩T+1≤γGn−3.Otherwise, we have the following seven possible cases by the symmetry (see Figure3).(1)
S∩Q=u5,u6,u9 (see Figure 3(a)); then, u3,u4,u11∈R are dominated by S∩T and S′∪v3,u4 could be a dominating set of Gn−5.It is obvious that at least one vertex ofv3,v4,u4 belongs to S to dominate v4. If v3∈S or u4∈S, then γGn−5≤S′∪v3,u4≤S′+1=γGn−3. If v4∈S, then S′v4∪v3,u4 is a dominating set of Gn−5 (in graph Gn, v10 is dominated by E0=v5i+1v5i+2,v5i+2v5i+3,v5i+4v5i+5,v5i+4u5i+4,v5i+5u5i+50≤i≤m−1,E1=E0\v5mu5m∪vn−1v0,v0u0,E2=E0\v5mu5m∪vn−1v0,vn−1un−1,v0u0,E3=E0∪vn−1v0,vn−1un−1,v0u0,E4=E0∪vn−2vn−1,vn−1v0,vn−2un−2,v0u0.). Thus, γGn−5≤S′+1=γGn−3.(2)
S∩Q=u5,u6,v9 (see Figure 3(b)); then, u3,u4,v10∈R are dominated by S∩T, and S′∪v3,v4 or S′∪u4,u10 can be a dominating set of Gn−5 in this case.For dominating vertexv4 in graph Gn, at least one vertex in v3,v4,u4 belongs to S. Hence, γGn−5≤S′+1=γGn−3.(3)
S∩Q=u5,v5,u9 (see Figure 3(c)), that is, u3,v4,u11∈R are dominated by S∩Q and u6,v7,v8,u8∈T are not dominated by S∩Q.Since the remaining one vertex inS′−S∩Q belongs to NGnv7, u4∈S or v6∈S to dominate u6. If v6∈S, then S∩T=u5,v5,v6,u9, and thus the vertex v8 cannot be dominated by S, a contradiction. If u4∈S, then S′∪u3 is a dominating set of Gn−5. So, γGn−5≤S′+1=γGn−3.(4)
S∩Q=u5,v5,v9 (see Figure 3(d)); then, u3,v4,v10∈R are dominated by S∩T and u6,v7,u8∈T are not dominated by S∩Q.Because the only one vertex inS∩NGnv7 cannot dominate u6 and u8 simultaneously, u4∈S or u10∈S. Actually, S′∪u4,u10 is a dominating set of Gn−5, which follows that γGn−5≤S′∪u4,u10≤S′+1=γGn−3.(5)
S∩Q=u5,u6,u8 (see Figure 3(e)); then, u3,u4,u10∈R are dominated by S∩T.At least one vertex ofv3,v4,u4 belongs to S to dominate v4. If u4∈S or v4∈S, then S′∪u3 is a dominating set of Gn−5. If v3∈S, then S′\v3∪u3,u4 is a dominating set of Gn−5. It follows that γGn−5≤S′+1=γGn−3.(6)
S∩Q=u6,v9,u9 (see Figure 3(f)); then, u4,v10,u11∈R are dominated by S∩T and v5,u5,v7,u8∈T are not dominated by S∩Q.The only one vertex inS∩NGnv7 cannot dominate v5 and u5 simultaneously; hence, v4∈S or u3∈S. For v4∈S, we get that S′∪v11 is a dominating set of Gn−5. In view of NGnv4\v5∩S≠∅, v3,u4,v4∩S≠∅. For u3∈S, S\v3∪v4,v11 is a γ-set of Gn if v3∈S, and S′∪v11 is a dominating set of Gn−5 if u4∈S or v4∈S. Therefore, γGn−5≤S′+1=γGn−3.(7)
S∩Q=u5,v5,u8 (see Figure 3(g)), that is, u3,v4,u10∈R are dominated by S∩Q and v7,v9,u9∈T are not dominated by S∩Q.Clearly,S′∪u3,v4 or S′∪v3,u3 is a dominating set of Gn−5 in this case. For dominating vertex v3 in graph Gn, we have that u3,v3,v4∩S≠∅. Hence, γGn−5≤S′+1=γGn−3.Case 3.
S
∩
T
=
3.
The vertices inS∩T can dominate at most two vertices in R; otherwise, (S ∩ T) ⊆ (S ∩ Q) , which means that v7 cannot be dominated by S. Therefore, S∩Q≤2.Subcase 5.
S
∩
Q
=
0. We have nothing to do, and S′ is a dominating set of Gn−5 and γGn−5≤S′=γGn−3.Subcase 6.
S
∩
Q
=
1. By symmetry, v3 or not, we have the following four cases (see Figure 4).(1)
S∩Q=v5 (see Figure 4(a)); then, v4∈R is dominated by S∩Q.The two vertices inS∩NGnv7 cannot dominate u6 and v9 at the same time; otherwise u7 cannot be dominated by S, a contradiction. Hence, at least one vertex of u4,v10 belongs to S′. Therefore, S′ is a dominating set of Gn−5 and γGn−5≤S′=γGn−3.(2)
S∩Q=u5 (see Figure 4(b)); then, u3∈R is dominated by S∩Q.The two vertices inS∩NGnv7 cannot dominate u6 and u9 at the same time, that is, S∩NGnv7≠v6,u7. Otherwise, v8 cannot be dominated by S, a contradiction.   Hence, at least one vertex of u4,u11 belongs to S′. In addition, u3,v3,v4∩S≠∅ for dominating u3 in graph Gn. If v3∈S or u3∈S, then S′ can be a dominating set of Gn−5. If v4∈S, in view of at least one vertex of u4,u11 belonging to S′, then S′\v4∪v3 is a dominating set of Gn−5. Therefore, γGn−5≤S′=γGn−3.(3)
S∩Q=u6 (see Figure 4(c)); then, u4∈R is dominated by S∩Q.The two vertices inS∩NGnv7 cannot dominate v5 and u9 at the same time; otherwise, v8 cannot be dominated by S, a contradiction. Hence, at least one vertex of v4,u11 belongs to S′. It implies that S′ is a dominating set of Gn−5 and γGn−5≤S′=γGn−3.(4)
S∩Q=u9 (see Figure 4(d)).
Ifv6∉S, then u4∈S to dominate u6. And S′ is a dominating set of Gn−5.
Ifv6∈S, then u7∉S; otherwise, NGnv8∩S=∅. Thus, u3∈S to dominate u5. Since NGnv4\v5∩S≠∅ and S\v3∪v4 is a dominating set of Gn, at least one vertex of v4,u4 belongs to S. If u4∈S, then S′ is a dominating set of Gn−5. If v4∈S, then S′\v4∪u4 is a dominating set of Gn−5.Subcase 7.
S
∩
Q
=
2; then, S∩NGnv7=1 and the vertices ⊚ should be dominated by the only one vertex in S∩NGnv7. We consider eleven possible cases.(1)
S∩Q=v5,u5 (see Figure 5(a)); then, v4,u3∈R is dominated by S∩Q.We claim thatS∩NGnv7≠v6; otherwise, v8 cannot be dominated by S. Hence, u4∈S for dominating u6. In addition, v3,u3,v4∩≠∅ to dominate v3. If v3∈S or u3∈S, then S′ is a dominating set of Gn−5. If v4∈S, then S′\v4∪v3 is a dominating set of Gn−5. Thus, γGn−5≤S′\v4∪v3|=γGn−3.(2)
S∩Q=v9,u9 (see Figure 5(b)); then, v10,u11∈R is dominated by S∩Q.IfS∩NGnv7=v8 or S∩NGnv7=u7, then v6 cannot be dominated by S, which is a contradiction to the definition of S. If S∩NGnv7=v7, then S−v7+v6 is a dominating set of Gn. Hence, we assume that S∩NGnv7=v6. Thus, S∪T=v6,v9,u9. Moreover, we get that u3,u10∈S to dominate u5 and u8, respectively. Since NGnv4\v5∩S≠∅, at least one vertex of v3,v4,u4belongs to S. If u4∈S, then S′ is a dominating set of Gn−5. If v4∈S or v3∈S, then i0=n−1,ifk=1,n+4−k,ifk=1mod5k≠1,n−k,ifk=2,4mod5,n−2−k,ifk=0,3mod5. or S′\v3∪u4 is a dominating set of Gn−5. Therefore,(16)γGn−5≤S′=γGn−3.(3)
S∩Q=v5,u9 (see Figure 5(c)).(4)
S∩Q=v5,v9 (see Figure 5(d)).(5)
S∩Q=u5,u9 (see Figure 5(e)).(6)
S∩Q=u6,u8 (see Figure 5(f)).For (3), (4), (5), and (6), it is obvious thatS′ is a dominating set of Gn−5.(7)
S∩Q=u6,u9 (see Figure 5(g)). S′\v4∪u4 is a dominating set of Gn−5.(8)
S∩Q=u6,v9 (see Figure 5(h)). S′ is a dominating set of Gn−5.(9)
S∩Q=u8,u9 (see Figure 5(i)).We claim thatS∩NGnv7=v6 or S∩NGnv7=v7. Since S−v7+v6 could be a dominating set of Gn, we assume that S∩NGnv7=v6. In addition, u3∈S for dominating u5. Since NGnv4\v5∩S≠∅ and S′\v3∪v4 is a dominating set of Gn, at least one vertex of v4,u4 belongs to S. For u4∈S, S′ is a dominating set of Gn−5. For v4∈S, S′\v4∪u4 is a dominating set of Gn−5. The result follows.(10)
S∩Q=u5,u6 (see Figure 5(j)); then, u11∈S.SinceNGnv3∩S≠∅, at least one vertex of v3,v4,u3 belongs to S. If v3∈S or u3∈S, then S′ is a dominating set of Gn−5. If v4∈S, then S′\v4∪v3 is a dominating set of Gn−5. Thus, γGn−5=γGn−5≤S\v4∪v3=γGn−3.(11)
S∩Q=u8,v9 (see Figure 5(k)). S′ is a dominating set of Gn−5.Case 4.
S
∩
T
=
2.
We say thatv7∈S; otherwise, S∩T≥3 to dominate the vertices in NGnv7. Hence, the vertices in S∩T have the following five cases by symmetry.(1)
S∩T=u5,v7 (see Figure 6(a)).(2)
S∩T=u6,v7 (see Figure 6(b)).(3)
S∩T=v5,v7 (see Figure 6(c)).(4)
S∩T=v6,v7 (see Figure 6(d)).In each of the above four circumstances,S′\v10 is a dominating set of Gn−5. Therefore, γGn−5≤S′\v10=γGn−3.(5)
S∩T=u7,v7 (see Figure 6(e)).
SinceNGnu11\u9∩S≠∅, at least one vertex of u11,v11,u13 belongs to S. If u11∈S or v11∈S, then S′\v10 is a dominating set of Gn−5. At least one vertex of v11,v12,v13,u12 belongs to S to dominate v12. If v12∈S or u12∈S, then S′\u10 is a dominating set of Gn−5.
Hence, we only need to considerv13,u13⊆S to dominate v12 and u11. Let A=v4,u4,v10,u10,v13,u13 and B=u3,u4,v11,u13,,u14. Then, we can deduce that A ⊆ S′, which is shown in Figure 6(f). Let S″ = (S′\A) ∪ B, which is shown in Figure 6(g). It is easy to verify that S″ is a dominating set of Gn−5 and γGn−5≤S″=S′−1=γGn−3.Case 5.
S
∩
T
=
1; then, S∩T=v7 and R⊆S. Hence, S′\v4,v10 is a dominating set of Gn−5 and γGn−5≤S′\v4,v10=γGn−3. This completes the proof.Lemma 3.
Let
n
=
5
m
+
t and Gn=Pn,2−v2. Then, γPn,2−v1v2,v2v3,v2u2>γPn,2 for i0=n−k,ifk=1,3mod5,n−1−k,ifk=0,2,4mod5..Proof.
It is sufficient to show thatγGn≥γPn,2 for t=0,3,4. Let S be a minimum dominating set of Gn. If NPn,2v2∩S≠∅, then S is a dominating set of Pn,2. Hence, γGn=S≥γPn,2.
In the following, we suppose thatS satisfies NPn,2v2∩S=∅. We prove Lemma 3 by using mathematical induction on m. There are at least three vertices in S to dominate the vertices in NPn,2v2=v1,u2,v3, at least one vertex of v0,u1, u0,u4, and u3,v4, respectively. Clearly, there are eight possible cases of these three vertices in S. By the symmetry of graph Gn, we only need to consider the following four cases: v0,u0,u3⊆S, v0,u0,v4⊆S, u0,u1,u3⊆S, and u0,u1,v4⊆S. Let m=1 and t=0. Then, γGn=S≥3=γPn,2. Let m=1 and t=3,4. It is easy to verify that γGn=S≥γPn,2 by analyzing the above four cases, respectively, and thus omitted here.
Assume that Lemma3 is true for m=k; we get that(17)γG5k+1+t≥γG5k+t+3≥5k+t−5k+t5−5k+t+25+3=5k+1+t−5k+1+t5−5k+1+t+25=γP5k+1+t,2,by Lemma 2. Therefore, The assertion holds for m=k+1. This completes the proof.Lemma 4 (see [34]).
b
G
≤
d
x
+
d
y
−
1 for any two adjacent vertices x and y in a graph G; that is,(18)bG≤minxy∈EGdGx+dGy−1.Theorem 2.
Ift=0,3,4, then bPn,2=3; if t=1,2, then 3≤bPn,2≤5.Proof.
By Lemma3, we have that γPn,2−v1v2,v2v3,v2u2>γPn,2 for t=0,3,4; thus, bPn,2≤3. By Lemma 4, bPn,2≤5 for t=1,2. Combining Theorem 1 gives that bPn,2=3 when t=0,3,4 and 3≤bPn,2≤5 when t=1,2. This completes the proof.Figure 2
The four possible cases ofS in Subcase 3.
(a)
(b)
(c)Figure 3
The seven possible cases ofS in Subcase 4.
(a)
(b)
(c)
(d)
(e)
(f)
(g)Figure 4
The four possible cases ofS in Subcase 6.
(a)
(b)
(c)
(d)Figure 5
The eleven possible cases ofS in Subcase 7.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)Figure 6
The four possible cases ofS in Subcase 6.
(a)
(b)
(c)
(d)
(e)
(f)
(g)



---

*Source: 7607856-2020-05-09.xml*