1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On the Equality of Domination Number and 2-Domination Number

Published Online: 22 Mar 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Feb 2021
Accepted: 15 Feb 2022
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The 2-domination number γ2(G) of a graph G is the minimum cardinality of a set DV (G) for which every vertex outside D is adjacent to at least two vertices in D. Clearly, γ2(G) cannot be smaller than the domination number γ(G). We consider a large class of graphs and characterize those members which satisfy γ2 = γ. For the general case, we prove that it is NP-hard to decide whether γ2 = γ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.

Keywords

MSC 2010

[1] J.D. Alvarado, S. Dantas and D. Rautenbach, Complexity of comparing the domination number to the independent domination, connected domination, and paired domination numbers, Mat. Contemp. 44 (2015) 1–8. https://doi.org/10.21711/231766362015/rmc445 Search in Google Scholar

[2] J.D. Alvarado, S. Dantas and D. Rautenbach, Perfectly relating the domination, total domination, and paired domination numbers of a graph, Discrete Math. 338 (2015) 1424–1431. https://doi.org/10.1016/j.disc.2015.03.01410.1016/j.disc.2015.03.014 Search in Google Scholar

[3] S. Arumugam, B.K. Jose, Cs. Bujtás and Zs. Tuza, Equality of domination and transversal numbers in hypergraphs, Discrete Appl. Math. 161 (2013) 1859–1867. https://doi.org/10.1016/j.dam.2013.02.00910.1016/j.dam.2013.02.009 Search in Google Scholar

[4] M. Blidia, M. Chellali and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, Discrete Math. 306 (2006) 1840–1845. https://doi.org/10.1016/j.disc.2006.03.06110.1016/j.disc.2006.03.061 Search in Google Scholar

[5] F. Bonomo, B. Brešar, L.N. Grippo, M. Milanič and M.D. Safe, Domination parameters with number 2: Interrelations and algorithmic consequences, Discrete Appl. Math. 235 (2018) 23–50. https://doi.org/10.1016/j.dam.2017.08.01710.1016/j.dam.2017.08.017 Search in Google Scholar

[6] Cs. Bujtás and S. Jaskó, Bounds on the 2-domination number, Discrete Appl. Math. 242 (2018) 4–15. https://doi.org/10.1016/j.dam.2017.05.01410.1016/j.dam.2017.05.014 Search in Google Scholar

[7] Y. Caro, On the k-domination and k-transversal numbers of graphs and hypergraphs, Ars Combin. 29 (1990) 49–55. Search in Google Scholar

[8] Y. Caro and Y. Roditty, A note on the k-domination number of a graph, Int. J. Math. Math. Sci. 13 (1990) 205–206. https://doi.org/10.1155/S016117129000031X10.1155/S016117129000031X Search in Google Scholar

[9] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-domination and k-independence in graphs: A survey, Graphs Combin. 28 (2012) 1–55. https://doi.org/10.1007/s00373-011-1040-310.1007/s00373-011-1040-3 Search in Google Scholar

[10] W.J. Desormeaux, M.A. Henning, D.F. Rall and A. Yeo, Relating the annihilation number and the 2-domination number of a tree, Discrete Math. 319 (2014) 15–23. https://doi.org/10.1016/j.disc.2013.11.02010.1016/j.disc.2013.11.020 Search in Google Scholar

[11] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. National Bureau of Standards B. 69B (1965) 125–130.10.6028/jres.069B.013 Search in Google Scholar

[12] G. Boruzanli Ekinci and Cs. Bujtás, Bipartite graphs with close domination and k-domination numbers, Open Math. 18 (2020) 873–885. https://doi.org/10.1515/math-2020-004710.1515/math-2020-0047 Search in Google Scholar

[13] O. Favaron, k-domination and k-independence in graphs, Ars Combin. 25C (1988) 159–167. Search in Google Scholar

[14] O. Favaron, A. Hansberg and L. Volkmann, On k-domination and minimum degree in graphs, J. Graph Theory 57 (2008) 33–40. https://doi.org/10.1002/jgt.2027910.1002/jgt.20279 Search in Google Scholar

[15] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory Appl. Algorithms Comput. Sci. (1985) 283–300. Search in Google Scholar

[16] J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, in: Graph Theory Appl. Algorithms Comput. Sci. (1985) 301–311. Search in Google Scholar

[17] M.R. Garey and D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness (WH Freeman and Co., New York, 1979). Search in Google Scholar

[18] A. Hansberg, On the k-domination number, the domination number and the cycle of length four, Util. Math. 98 (2015) 65–76. Search in Google Scholar

[19] A. Hansberg and R. Pepper, On k-domination and j-independence in graphs, Discrete Appl. Math. 161 (2013) 1472–1480. https://doi.org/10.1016/j.dam.2013.02.00810.1016/j.dam.2013.02.008 Search in Google Scholar

[20] A. Hansberg, B. Randerath and L. Volkmann, Claw-free graphs with equal 2-domination and domination numbers, Filomat 30 (2016) 2795–2801. https://doi.org/10.2298/FIL1610795H10.2298/FIL1610795H Search in Google Scholar

[21] A. Hansberg and L. Volkmann, On graphs with equal domination and 2-domination numbers, Discrete Math. 308 (2008) 2277–2281. https://doi.org/10.1016/j.disc.2007.04.05710.1016/j.disc.2007.04.057 Search in Google Scholar

[22] B. Hartnell and D.F. Rall, A characterization of graphs in which some minimum dominating set covers all the edges, Czechoslovak Math. J. 45 (1995) 221–230. https://doi.org/10.21136/CMJ.1995.12852610.21136/CMJ.1995.128526 Search in Google Scholar

[23] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, 1997). Search in Google Scholar

[24] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (CRC Press, 1998).10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F Search in Google Scholar

[25] M.A. Henning, S. Jäger and D. Rautenbach, Hereditary equality of domination and exponential domination, Discuss. Math. Graph Theory 38 (2018) 275–285. https://doi.org/10.7151/dmgt.200610.7151/dmgt.2006 Search in Google Scholar

[26] M. Krzywkowski, M.A. Henning and C. Brause, A characterization of trees with equal 2-domination and 2-independence numbers, Discrete Math. Theor. Comput. Sci. 19 (2017). https://doi.org/10.23638/DMTCS-19-1-1 Search in Google Scholar

[27] D. Marx, The complexity of chromatic strength and chromatic edge strength, Comput. Complexity 14 (2006) 308–340. https://doi.org/10.1007/s00037-005-0201-210.1007/s00037-005-0201-2 Search in Google Scholar

[28] S. Micali and V.V. Vazirani, An O(| V || E |) O\left( {\sqrt {\left| V \right|} \cdot \left| E \right|} \right) algorithm for finding maximum matching in general graphs, in: Proc. 21st Annual Symp. Found. Comput. Sci., (IEEE, New York, USA, 1980) 17–27. https://doi.org/10.1109/SFCS.1980.1210.1109/SFCS.1980.12 Search in Google Scholar

[29] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and covering number, Discrete Math. 191 (1998) 159–169. https://doi.org/10.1016/S0012-365X(98)00103-410.1016/S0012-365X(98)00103-4 Search in Google Scholar

[30] R.S. Shaheen, Bounds for the 2-domination number of toroidal grid graphs, Int. J. Comput. Math. 86 (2009) 584–588. https://doi.org/10.1080/0020716070169028410.1080/00207160701690284 Search in Google Scholar

[31] D.B. West, Introduction to Graph Theory, 2nd Ed. (Prentice-Hall, Upper Saddle River, 2001). Search in Google Scholar

[32] J. Yue, S. Zhang, Y. Zhu, S. Klavžar and Y. Shi, The annihilation number does not bound the 2-domination number from the above, Discrete Math. 343 (2020) 111707. https://doi.org/10.1016/j.disc.2019.11170710.1016/j.disc.2019.111707 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo