Bondage number of mesh networks

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 P_n × P_m the Cartesian product of two paths P_n and P_m. This paper determines the exact values of b(P_n × P₂), b(P_n × P₃), and b(P_n × P₄) for n ⩾ 2.

Keywords

Bondage number / dominating set / domination number / mesh network

References

[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 C₅ × C_n. 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. Haynes T. W., Hedetniemi S. T., Slater P. J. Bondage, insensitivity, and reinforcement. Domination in Graphs: Advanced Topics, 1998, New York: Marcel Dekker, 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), 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

[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 C_n × C₄. 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 C₃ × C_n. 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, 2001, Dordrecht /Boston/London: Kluwer Academic Publishers

[31] Xu J. -M. Theory and Application of Graphs, 2003, Dordrecht/Boston/London: Kluwer Academic Publishers

[32] Zhang X., Liu J., Meng J. -X. The bondage number in complete t-partite digraphs. Inform Process Lett, 2009, 109(17): 997-1000