×

Bondage number of the strong product of two trees. (English) Zbl 1368.05123

Summary: The bondage number \(b(G)\) of a nonempty graph \(G\) is the cardinality of a minimum set of edges whose removal from \(G\) results in a graph with domination number greater than that of \(G\). It is known that \(b(T) \leq 2\) for any nontrivial tree \(T\). In this paper, we obtain that the bondage number of the strong product of two nontrivial trees \(b(T \boxtimes T^\prime)\) is equal to \(b(T) b(T^\prime)\) or \(b(T) b(T^\prime) + 1\), which implies that \(b(T \boxtimes T^\prime)\) is equal to 1, 2, 3, 4 or 5.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauer, D.; Harary, F.; Nieminen, J.; Suffel, C. L., Domination alteration sets in graphs, Discrete Math., 47, 2-3, 153-161 (1983) · Zbl 0524.05040
[2] Cao, J. X.; Yuan, X. D.; Sohn, M. Y., Domination and bondage number of \(C_5 \times C_n\), Ars Combin., 97A, 299-310 (2010) · Zbl 1249.05278
[3] Dettlaff, M.; Lemańska, M.; Yero, I. G., Bondage number of grid graphs, Discrete Appl. Math., 167, 94-99 (2014) · Zbl 1284.05195
[4] Dunbar, J. E.; Haynes, T. W.; Teschner, U.; Volkmann, L., Bondage, insensitivity, and reinforcement, (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. L., Domination in Graphs Advanced Topics (1998), Marcel Dekker: Marcel Dekker New York), 471-489 · Zbl 0894.05025
[5] Fink, J. F.; Jacobson, M. S.; Kinch, L. F.; Roberts, J., The bondage number of a graph, Discrete Math., 86, 1-3, 47-57 (1990) · Zbl 0745.05056
[6] Hammack, R.; Imrich, W.; Klavžar, S., Handbook of Product Graphs (2011), CRC Press: CRC Press New York-London · Zbl 1283.05001
[7] Hartnell, B. L.; Rall, D. F., Bounds on the bondage number of a graph, Discrete Math., 128, 1-3, 173-177 (1994) · Zbl 0796.05051
[8] Hu, F. T.; Xu, J. M., The bondage number of mesh network, Front. Math. China, 7, 5, 813-826 (2012) · Zbl 1254.05075
[9] Hu, F. T.; Xu, J. M., On the complexity of the bondage and reinforcement problems, J. Complexity, 28, 2, 192-201 (2012) · Zbl 1239.05138
[10] Kang, L. Y.; Sohn, M. Y.; Kim, H. K., Bondage number of the discrete torus \(C_n \times C_4\), Discrete Math., 303, 1-3, 80-86 (2005) · Zbl 1077.05077
[11] Nowakowski, R. J.; Rall, D. F., Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory, 16, 1, 53-79 (1996) · Zbl 0865.05071
[12] Sohn, M. Y.; Yuan, X. D.; Jeong, H. S., The bondage number of \(C_3 \times C_n\), J. Korean Math. Soc., 44, 6, 1213-1231 (2007) · Zbl 1139.05037
[13] Teschner, U., The bondage number of a graph \(G\) can be much greater than \(\Delta(G)\), Ars Combin., 43, 81-87 (1996) · Zbl 0881.05062
[14] Teschner, U., New results about the bondage number of a graph, Discrete Math., 171, 1-3, 249-259 (1997) · Zbl 0881.05067
[15] Xu, J. M., On bondage number of graphs: a survey with some comments, Int. J. Comb., 2013 (2013), Article ID 595210, 34 pages
[16] Yang, C.; Xu, J. M., Connectivity and edge-connectivity of strong product graphs, J. Univ. Sci. Technol. China, 38, 5, 449-455 (2008) · Zbl 1174.05435
[17] Zhao, W. S., Domination Number and Restricted Edge Connectivity of Product Graphs (2010), Wuyi University
[19] Zhao, W. S.; Zhang, H. P., The bondage number of the strong product of two paths, Front. Math. China., 10, 2, 435-460 (2015) · Zbl 1326.05116
[20] Zhao, W. S.; Zhang, H. P., The bondage number of the strong product of a complete graph with a path and a special starlike tree, Discrete Math. Algorithms Appl., 8, 1, 1650006 (2016), (14 pages) · Zbl 1338.05204
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.