Applied Mathematics, 2010, 1, 101-103
doi:10.4236/am.2010.12013 Published Online July 2010 (http://www. SciRP.org/journal/am)
Bondage Number of 1-Planar Graph*
Qiaoling Ma, Sumei Zhang, Jihui Wang†
School of Science, University of Jinan, Jinan, China
Received May 8, 2010; revised June 1, 2010; accepted June 11, 2010
Abstract
The bondage number )(Gb of a nonempty graph G is the cardinality of a smallest set of edges whose re-
moval from G results in a graph a domination number greater than the domination number of G. In this paper,
we prove that 12)( Gb for a 1-planar graph G.
Keywords: Domination Number, Bondage number, 1-Planar Graph, Combinatorial Problem
1. Introduction
Throughout this paper, we consider connected graphs
without loops or multiple edges. A 1-planar graph is a
graph which can be drawn on the plane so that every
edge crosses at most one other edge. For a graph G,
)(GV and )(GE are used to denote the vertex set and
edge set of G, respectively. The degree of a vertex u in G
is denoted by )(ud . For a vertex subset )( GVS ,
define )(SN {xV(G)\ S | there is a y  S such
that xy )(GE}. When S = {v}, we write

)(vN
)(SN for short. The minimum degree of vertices in G is
denoted by )(G  and the maximum degree by )(G.
The distance between two vertices u and v in G is de-
noted by ),( vud. For a subset )(GVX , ][XG
denotes the subgraph of G induced by X.
A subset D of )(GV is called a dominating set, if
)()( GVDND . The domination number of G, de-
noted by )(G

, is the minimum cardinality of a domi-
nating set. The bondage number )( Gb of a nonempty
graph G is the cardinality of a smallest set of edges
whose removal from G results in a graph with domina-
tion number greater than )(G

.
The bondage number was first introduced by Bauer et
al. [1] in 1983. The following two main outstanding con-
jectures on bondage number were formulated by Tesch-
ner [2].
Conjecture 1.1 If G is a planar graph, then

)(Gb
1)(


G.
Conjecture 1.2 For any graph G, )(
2
3
)( GGb  .
In 2000, Kang and Yuan [3] proved that min)(

Gb

 2)(,8


G for any planar graph. That is, conjecture
1.1 is showed for planar graph with 7)(  G. Up to
now, conjecture 1.1 is still open for planar graph G with
6)(


G. Conjecture 1.2 is still open. In this paper, we
prove that 12)(

Gb for a 1-planar graph G.
2. Preliminary Results
First of all, we recall some useful results that we will
need
Lemma 2.1 [4] If G is a graph, then for every pair of
adjacent vertices u and v in G, then )()()( vdudGb


)()(1vNuN  .
Lemma 2.2 [5,6] If u and v are two vertices of G with
2),(

vud , then 1)()()( 

vdudGb.
Lemma 2.3 [7] Let G be a 1-planar graph, then
7)(

G

.
Lemma 2.4 [7] Let G be a 1-planar graph on n verti-
ces and m edges, then 84 

nm .
Lemma 2.5 Let G be a bipartite 1-planar graph on n
vertices and m edges, then 63 nm .
Proof. Without loss of generality, let G be a maximal
bipartite 1-planar graph on n vertices and X, Y is a bipar-
tition of graph G. Form a 1-planar graph G from G as
follows: add some edges to join vertices in X, and add
some edges to join the vertices in Y, such that G

is a
maximal 1-planar graph with GG  . By the maximal-
*This work was supported by NSFC (10901097) and the Nature Sci-
ence Foundation of Shandong Province (Y2008A20), also was sup-
p
orted by the Scientific Research and Development Project of Shan-
dong Provincial Education Department (TJY0706) and the Science and
Technology Foundation of University of Jinan (XKY0705).

Q. L. MA ET AL.
102
ity of G, the subgraph ][ XG

and ][YG must be
connected. Then we have
1])[(,1])[( 


YYGEXXGE .
By lemma 2.4, 84)( 
nGE. So
])[(])[()()( YGEXGEGEGE  




631184 nYXn .
This completes the prove of lemma 2.5.
3. Bondage Number of 1-Planar Graph
Theorem 3.1 If G is a 1-planar graph, then 12)(

Gb .
Proof. Suppose to the contrary that G is a 1-planar
graph with 13)( Gb . Then we have
Claim 1. For two distinct vertices y
x
, of G, if
 7)(),(maxydxd , and  6)(),(min ydxd , then it
must be the case that 3),( yxd.
Otherwise, 2),( yxd. But then, by lemma 2.2,
121)()()(  ydxdGb , a contradiction.
Claim 2. If there is some )( GVx such that
5)( xd then 9)( yd for all )(xNy .
Otherwise, 121851)()()(


 ydxdGb ,
a contradiction.
Now, we define
 5)(|)(
1xdGVxV ,
 6)(|)(
2xdGVxV ,
 7)(|)(
3 xdGVxV.
Let 3 VA  be the maximum and such that A is in-
dependent of G. By Claim 1 and the maximality of A, we
have also
Claim 3. 2
() ()NVN A

 and )(
3ANAV,
Let

k
xxxAV  212 ,, and 1 VGH . Define
HH 
0,
.1,
1kiFHH iii  
where 
)(,),(,| 1  iixi HExyyxxNyxxyEF i such
that iii HFH 
1 is still a 1-planar graph and such
that )]([ ii xNH is 2-connected. It is easy to see that
)]([ ikxNH is still 2-connected for ki1.
Claim 4. If 2
V

, then for each vertex )( 2
VNv

,
v is of degree at least 9 in k H.
In fact, let 2
Vx  and )(xNv

. If )()( xNvN 

 in G, then by lemma 2.2, 131)()( 

xdvd ,
and 8)(14)(


xdvd , by the 2-connectivity of
)]([xNHk, v is of degree at least 10 in k H. If )( vN
()Nx


, then by lemma 2.1, 132)()( 

xdvd .
Then 9)( vd .
Analogously, we have
Claim 5. If A


, then for each vertex )(ANv

, v
is of degree at least 9 in k
H.
Now, 2
VHGk


 is a 1-planar graph, satisfying
(a) The minimum degree of 
G is 7,
(b)


7)(|)( 



vdGVvAG,
(c) A is independent of 
G,
(d) For every vertex 9)(),()( 

 vdANANv GG .
Let

 )(,|)()( ANyAxGExyA 



. Then
))();(,( AANA

is a bipartite 1-planar graph with A7
edges. By lemma 2.5,
6)(337 ANAA .
Hence
2
3
4
)(  AAN
.
Then we have
)(
2
1
)(
)(
vdGE
GVv
G




)))()((8)(97(
2
1ANAGVANA  
AANGV 2
1
)(
2
1
)(4 
1
6
1
)(4  AGV
8)(4   GV .
A contradiction.
This completes the proof of the theorem.
Theorem 3.2 If G is a 1-planar graph and there is no
degree seven vertex, then 11)( Gb.
Proof. Suppose to the contrary that 12)( Gb .
Let

 6)(|)( 


vdGVvX , and suppose that


k
xxxX 
21,

By lemma 2.2, for any two distinct vertices Xyx

,,
3),( yxd.
Define
G
H

0,
kiFHH iii 


1, 1.
where

 )(,),(,| 1 


iixi HExyyxxNyxxyE
F
i such

Q. L. MA ET AL.
103
that iii HFH
1 is still a 1-planar graph and such
that )]([ ii xNH is 2-connected when 3)(
i
xd .
Now, by lemma 2.1 and 2.2, for any
)
(, yNyXx

,
if 2)( xd then 11)(yd and so y is of degree at
least 11 in k
H; If 3)( xd and 1)()( yNxN ,
then 8)( yd and so y is of degree at least 9 in k
H;
If 3)( xd and 2)()( yNxN , then 9)( yd
and So y is of degree at least 9 in k
H.
By the construction of k
H, we know that k H is a
1-planar graph. But XHk is a 1-planar graph with a
minimum degree of at least 8. It contradicts with lemma
2.3, and the proof is completed.
4. References
[1] D. Bauer. F. Harry, J. Nieminen and C. L. Suffel, “Domi-
nation Alteration Sets in Graphs,” Discrete Mathematics,
Vol. 47, 1983, pp. 153-161.
[2] U. Teschner, “A New Upper Bound for the Bondage
Number of Graphs with Small Domination Number,”
Australasian Journal of Combinatorics, Vol. 12, 1995, pp.
27-35.
[3] L. Kang and J. Yuan, “Bondage Number of Planar
Graphs,” Discrete Mathematics, Vol. 222, No. 1-3, 2000,
pp. 191-198.
[4] B. L. Hartnell and D. F. Rall, “Bounds on the Bondage
Number of a Graph,” Discrete Mathematics, Vol. 128,
No. 1-3, 1994, pp. 173-177.
[5] B. L. Hartnell and D. F. Rall, “A Bound on the Size of a
Graph with Given Order and Bondage Number,” Discrete
Mathematics, Vol. 197/198, 1999, pp. 409-413.
[6] U. Teschner, “New Results about the Bondage Number of
a Graph,” Discrete Mathematics, Vol. 171, No. 1-3, 1997,
pp. 249-259.
[7] I. Fabrici, “The Structure of 1-Planar Graphs,” Discrete
Mathematics, Vol. 307, No. 1, 2007, pp. 854-865.