Frontiers of Mathematics in China >
Bondage number of mesh networks
Received date: 22 Apr 2011
Accepted date: 22 Nov 2011
Published date: 01 Oct 2012
Copyright
The bondage number b(G) of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number greater than that of G. Denote Pn × Pm the Cartesian product of two paths Pn and Pm. This paper determines the exact values of b(Pn × P2), b(Pn × P3), and b(Pn × P4) for n≥2.
Key words： Bondage number; dominating set; domination number; mesh network
Futao HU , Jun-Ming XU . Bondage number of mesh networks[J]. Frontiers of Mathematics in China, 2012 , 7(5) : 813 -826 . DOI: 10.1007/s11464-012-0173-x
| 1 |
Bauer D, Harary F, Nieminen J, Suffel C L. Domination alteration sets in graphs. Discrete Math, 1983, 47: 153-161
|
| 2 |
Cao J X, Yuan X D, Sohn M Y. Domination and bondage number of C5 × Cn. Ars Combin, 2010, 97A: 299-310
|
| 3 |
Cao Y-C, Huang J, Xu J-M. The bondage number of graphs with crossing number less than four. Ars Combin (to appear)
|
| 4 |
Carlson K, Develin M. On the bondage number of planar and directed graphs. Discrete Math, 2006, 306(8-9): 820-826
|
| 5 |
Chang T Y, Clark W E. The domination numbers of the 5 × n and 6 × n grid graphs. J Graph Theory, 1993, 17: 81-107
|
| 6 |
Chang T Y, Clark W E, Hare E O. Domination numbers of complete grid graphs, I. Ars Combin, 1994, 38: 97-111
|
| 7 |
Dunbar J E, Haynes T W, Teschner U, Volkmann L. Bondage, insensitivity, and reinforcement. In: Haynes T W, Hedetniemi S T, Slater P J, eds. Domination in Graphs: Advanced Topics. Monogr Textbooks Pure Appl Math, 209. New York: Marcel Dekker, 1998, 471-489
|
| 8 |
Fink J F, Jacobson M S, Kinch L F, Roberts J. The bondage number of a graph. Discrete Math, 1990, 86: 47-57
|
| 9 |
Gonçalves D, Pinlou A, Rao M, Thomassé S. The domination number of grid graphs. SIAM J Discrete Math (to appear)
|
| 10 |
Hartnell B L, Jorgensen L K, Vestergaard P D, Whitehead C. Edge stability of the k-domination number of trees. Bull Inst Combin Appl, 1998, 22: 31-40
|
| 11 |
Hartnell B L, Rall D F. A characterization of trees in which no edge is essential to the domination number. Ars Combin, 1992, 33: 65-76
|
| 12 |
Hartnell B L, Rall D F. Bounds on the bondage number of a graph. Discrete Math, 1994, 128: 173-177
|
| 13 |
Hattingh J H, Plummer A R. Restrained bondage in graphs. Discrete Math, 2008, 308(23): 5446-5453
|
| 14 |
Hu F-T, Xu J-M. On the complexity of the bondage and reinforcement problems. J Complexity (to appear),
|
| 15 |
Huang J, Xu J-M. The bondage numbers of extended de Bruijn and Kautz digraphs. Comput Math Appl, 2006, 51(6-7): 1137-1147
|
| 16 |
Huang J, Xu J-M. The bondage number of graphs with small crossing number. Discrete Math, 2007, 307(14): 1881-1897
|
| 17 |
Huang J, Xu J-M. The total domination and bondage numbers of extended de Bruijn and Kautz digraphs. Comput Math Appl, 2007, 53(8): 1206-1213
|
| 18 |
Huang J, Xu J-M. The bondage numbers and efficient dominations of vertex-transitive graphs. Discrete Math, 2008, 308(4): 571-582
|
| 19 |
Jacobson M S, Kinch L F. On the domination number of products of graphs I. Ars Combin, 1984, 18: 33-44
|
| 20 |
Kang L-Y, Sohn M Y, Kim H K. Bondage number of the discrete torus Cn × C4. Discrete Math, 2005, 303: 80-86
|
| 21 |
Kang L-Y, Yuan J-J. Bondage number of planar graphs. Discrete Math, 2000, 222: 191-198
|
| 22 |
Klaviar S, Seifter N. Dominating Cartesian products of cycles. Discrete Appl Math, 1995, 59: 129-136
|
| 23 |
Raczek J. Paired bondage in trees. Discrete Math, 2008, 308(23): 5570-5575
|
| 24 |
Sohn M Y, Yuan X D, Jeong H S. The bondage number of C3 × Cn. J Korean Math Soc, 2007, 44(6): 1213-1231
|
| 25 |
Teschner U. A new upper bound for the bondage number of graphs with small domination number. The Australas J Combin, 1995, 12: 27-35
|
| 26 |
Teschner U. The bondage number of a graph G can be much greater than Δ(G). Ars Combin, 1996, 43: 81-87
|
| 27 |
Teschner U. New results about the bondage number of a graph. Discrete Math, 1997, 171: 249-259
|
| 28 |
Teschner U. On the bondage number of block graphs. Ars Combin, 1997, 46: 25-32
|
| 29 |
Topp J, Vestergaard P D. αk and γk-stable graphs. Discrete Math, 2000, 212: 149-160
|
| 30 |
Xu J-M. Topological Structure and Analysis of Interconnection Networks. Dordrecht /Boston/London: Kluwer Academic Publishers, 2001
|
| 31 |
Xu J-M. Theory and Application of Graphs. Dordrecht/Boston/London: Kluwer Academic Publishers, 2003
|
| 32 |
Zhang X, Liu J, Meng J-X. The bondage number in complete t-partite digraphs. Inform Process Lett, 2009, 109(17): 997-1000
|
/
| 〈 |
|
〉 |