DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

G. Boruzanlı Ekinci

Gülnaz Boruzanlı Ekinci

Ege University

email: gulnazboruzanli@gmail.com

0000-0002-6733-6321

Cs. Bujtás

Csilla Bujtás

Department of Mathematics, University of Ljubljana,
Jadranska 19,
Ljubljana 1000, Slovenia

email: csilla.bujtas@fmf.uni-lj.si

0000-0002-0511-5291

Title:

On the equality of domination number and 2-domination number

PDF

Source:

Discussiones Mathematicae Graph Theory 44(1) (2024) 383-406

Received: 2021-02-01 , Revised: 2022-02-13 , Accepted: 2022-02-15 , Available online: 2022-03-11 , https://doi.org/10.7151/dmgt.2452

Abstract:

The $2$-domination number $\gamma_2(G)$ of a graph $G$ is the minimum cardinality of a set $D\subseteq V(G)$ for which every vertex outside $D$ is adjacent to at least two vertices in $D$. Clearly, $\gamma_2(G)$ cannot be smaller than the domination number $\gamma(G)$. We consider a large class of graphs and characterize those members which satisfy $\gamma_2=\gamma$. For the general case, we prove that it is NP-hard to decide whether $\gamma_2=\gamma$ 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

References:

  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
Close