Geodesic
On the equality of domination number and 2-domination number
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 383-406 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

The 2-domination number γ_2(G) of a graph G is the minimum cardinality of a set D⊆ V(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: domination number, $2$-domination number, hereditary property, computational complexity 
@article{DMGT_2024_44_1_a19,
     author = {Boruzanl{\i} Ekinci, G\"ulnaz and Bujt\'as, Csilla},
     title = {On the equality of domination number and 2-domination number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {383--406},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/}
}
TY  - JOUR
AU  - Boruzanlı Ekinci, Gülnaz
AU  - Bujtás, Csilla
TI  - On the equality of domination number and 2-domination number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 383
EP  - 406
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/
LA  - en
ID  - DMGT_2024_44_1_a19
ER  - 
%0 Journal Article
%A Boruzanlı Ekinci, Gülnaz
%A Bujtás, Csilla
%T On the equality of domination number and 2-domination number
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 383-406
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/
%G en
%F DMGT_2024_44_1_a19
Boruzanlı Ekinci, Gülnaz; Bujtás, Csilla. On the equality of domination number and 2-domination number. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 383-406. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a19/

[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

[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.014

[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.009

[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.061

[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.017

[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.014

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

[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/S016117129000031X

[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-3

[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.020

[11] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. National Bureau of Standards B. 69B (1965) 125–130.

[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-0047

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

[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.20279

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

[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.

[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).

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

[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.008

[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/FIL1610795H

[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.057

[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.128526

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

[24] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (CRC Press, 1998).

[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.2006

[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

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

[28] S. Micali and V.V. Vazirani, An $O(\sqrt{|V|} \cdot|E|)$ 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.12

[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-4

[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/00207160701690284

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

[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.111707