Frontiers of Mathematics in China >
Bondage number of strong product of two paths
Received date: 25 Apr 2013
Accepted date: 21 May 2014
Published date: 12 Feb 2015
Copyright
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(PmPn) = 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).
Key words： Bondage number; strong product; path
Weisheng ZHAO , Heping ZHANG . Bondage number of strong product of two paths[J]. Frontiers of Mathematics in China, 2015 , 10(2) : 435 -460 . DOI: 10.1007/s11464-014-0391-5
| 1 |
Cao J X, Yuan X D, Sohn M Y. Domination and bondage number of C5 × Cn.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 Cn × C4.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 C3 × Cn.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
|
/
| 〈 |
|
〉 |