### Paper Menu >>

### Journal Menu >>

Applied Mathematics, 2010, 1, 101-103 doi:10.4236/am.2010.12013 Published Online July 2010 (http://www. SciRP.org/journal/am) Copyright © 2010 SciRes. AM Bondage Number of 1-Planar Graph* Qiaoling Ma, Sumei Zhang, Jihui Wang† School of Science, University of Jinan, Jinan, China E-mail: wangjh@ujn.edu.cn 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 {xV(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. Copyright © 2010 SciRes. AM 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)(),(maxydxd , 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)(|)( 1xdGVxV , 6)(|)( 2xdGVxV , 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 ki1. 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. Copyright © 2010 SciRes. AM 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. |