|
|
|
Bondage number of mesh networks |
Futao HU, Jun-Ming XU( ) |
| School of Mathematical Sciences, University of Science and Technology of China;Wentsun Wu Key Laboratory of Chinese Academy of Sciences, Hefei 230026, China |
|
|
|
|
Abstract 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.
|
| Keywords
Bondage number
dominating set
domination number
mesh network
|
|
Corresponding Author(s):
XU Jun-Ming,Email:xujm@ustc.edu.cn
|
|
Issue Date: 01 October 2012
|
|
| 1 |
Bauer D, Harary F, Nieminen J, Suffel C L. Domination alteration sets in graphs. Discrete Math , 1983, 47: 153-161
doi: 10.1016/0012-365X(83)90085-7
|
| 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
doi: 10.1016/j.disc.2006.02.008
|
| 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
doi: 10.1002/jgt.3190170110
|
| 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
doi: 10.1016/0012-365X(90)90348-L
|
| 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
doi: 10.1016/0012-365X(94)90111-2
|
| 13 |
Hattingh J H, Plummer A R. Restrained bondage in graphs. Discrete Math , 2008, 308(23): 5446-5453
doi: 10.1016/j.disc.2007.10.016
|
| 14 |
Hu F-T, Xu J-M. On the complexity of the bondage and reinforcement problems. J Complexity (to appear), pmid:10.1016/j.jco.2011.11.001" target="blank">
doi: 10.1016/j.jco.2011.11.001 pmid:10.1016/j.jco.2011.11.001" target="blank">
doi: 10.1016/j.jco.2011.11.001
|
| 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
doi: 10.1016/j.camwa.2005.10.015
|
| 16 |
Huang J, Xu J-M. The bondage number of graphs with small crossing number. Discrete Math , 2007, 307(14): 1881-1897
doi: 10.1016/j.disc.2006.09.035
|
| 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
doi: 10.1016/j.camwa.2006.05.020
|
| 18 |
Huang J, Xu J-M. The bondage numbers and efficient dominations of vertex-transitive graphs. Discrete Math , 2008, 308(4): 571-582
doi: 10.1016/j.disc.2007.03.027
|
| 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
doi: 10.1016/j.disc.2004.12.019
|
| 21 |
Kang L-Y, Yuan J-J. Bondage number of planar graphs. Discrete Math , 2000, 222: 191-198
doi: 10.1016/S0012-365X(99)00405-7
|
| 22 |
Klaviar S, Seifter N. Dominating Cartesian products of cycles. Discrete Appl Math , 1995, 59: 129-136
doi: 10.1016/0166-218X(93)E0167-W
|
| 23 |
Raczek J. Paired bondage in trees. Discrete Math , 2008, 308(23): 5570-5575
doi: 10.1016/j.disc.2007.10.010
|
| 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
doi: 10.4134/JKMS.2007.44.6.1213
|
| 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
doi: 10.1016/S0012-365X(96)00007-6
|
| 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
doi: 10.1016/S0012-365X(99)00216-2
|
| 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
doi: 10.1016/j.ipl.2009.06.002
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
