Bondage number of strong product of two paths

Abstract

The bondage number b(G) of a graph G is the cardinality of a minimum set of edges whose removal from G results in a graph with a domination number greater than that of G. In this paper, we obtain the exact value of the bondage number of the strong product of two paths. That is, for any two positive integers m≥2 and n≥2, b(P_m⊠P_n) = 7 - r(m) - r(n) if (r(m), r(n)) = (1, 1) or (3, 3), 6 - r(m) - r(n) otherwise, where r(t) is a function of positive integer t, defined as r(t) = 1 if t ≡ 1 (mod 3), r(t) = 2 if t ≡ 2 (mod 3), and r(t) = 3 if t ≡ 0 (mod 3).

Keywords

Bondage number / strong product / path

References

[1] Cao J X, Yuan X D, Sohn M Y. Domination and bondage number of C₅ × C_n.Ars Combin, 2010, 97A: 299-310

[2] 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

[3] Fink J F, Jacobson M S, Kinch L F, Roberts J. The bondage number of a graph. Discrete Math, 1990, 86: 47-57

[4] Hammack R, Imrich W, Klavžar S. Handbook of Product Graphs. New York-London: CRC Press, 2011

[5] 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

[6] Hu F T, Xu J M. On the complexity of the bondage and reinforcement problems. J Complexity, 2012, 28: 192-201

[7] Hu F T, Xu J M. Bondage number of mesh networks. Front Math China, 2012, 7(5): 813-826

[8] Huang J, Xu J M. The bondage numbers of extended de Bruijn and Kautz digraphs. Comput Math Appl, 2006, 516(7): 1137-1147

[9] Huang J, Xu J M. The bondage numbers and efficient dominations of vertex-transitive graphs. Discrete Math, 2008, 308(4): 571-582

[10] Jacobson M S, Kinch L F. On the domination number of products of graphs I. Ars Combin, 1984, 18: 33-44

[11] Kang L Y, Sohn M Y, Kim H K. Bondage number of the discrete torus C_n × C₄.Discrete Math, 2005, 303: 80-86

[12] Meir A, Moon J W. Relations between packing and covering numbers of a tree. Pacific J Math, 1975, 61: 225-233

[13] Nowakowski R J, Rall D F. Associative graph products and their independence, domination and coloring numbers. Discuss Math Graph Theory, 1996, 16: 53-79

[14] 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

[15] Teschner U. New results about the bondage number of a graph. Discrete Math, 1997, 171: 249-259

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

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg