Domination parameters of graph covers

Articles in Press

Document Type : Original paper

Author

Department of Mathematical and Physical Sciences, La Trobe University, Bendigo, Australia

Abstract

A graph $G$ is a \emph{cover} of a graph $F$ if there exists an onto mapping $\pi : V(G) \to V(F)$, called a (\emph{covering}) \emph{projection}, such that $\pi$ maps the neighbours of any vertex $v$ in $G$ bijectively onto the neighbours of $\pi(v)$ in $F$. This paper is the first attempt to study the connection between domination parameters and graph covers. We focus on the domination number, the total domination number, and the connected domination number. We prove upper and lower bounds for the domination parameters of $G$. Moreover, we propose a conjecture on the lower bound for the domination number of $G$ and provide evidence to support the conjecture.

Keywords

Main Subjects

References

[1] A. Amit and N. Linial, Random graph coverings I: General theory and graph connectivity, Combinatorica 22 (2002), no. 1, 1–18. https://doi.org/10.1007/s004930200000
[2] A. Amit, N. Linial, J. Matoušek, and E. Rozenman, Random lifts of graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, Citeseer, 2001, pp. 883–894.
[3] D. Annor, Y. Nikolayevsky, and M.S. Payne, Three theorems on Negami’s planar cover conjecture, arXiv preprint arXiv:2412.19560 (2024).
[4] D. Archdeacon and R. Bruce Richter, On the parity of planar covers, J. Graph Theory 14 (1990), no. 2, 199–204. https://doi.org/10.1002/jgt.3190140208
[5] D. Archdeacon, J. Ellis-Monaghan, D. Fisher, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, and R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004), no. 3, 207–210. https://doi.org/10.1002/jgt.20000
[6] R.C. Brigham, P.Z. Chinn, and R.D. Dutton, Vertex domination-critical graphs, Networks 18 (1988), no. 3, 173–179.
https://doi.org/10.1002/net.3230180304
[7] C. Bujtás, Domination number of graphs with minimum degree five, Discuss. Math. Graph Theory 41 (2021), no. 3, 763 –777. https://doi.org/10.7151/dmgt.2339
[8] V. Chvátal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992), no. 1, 19–26. https://doi.org/10.1007/BF01191201
[9] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980), no. 3, 211–219.
https://doi.org/10.1002/net.3230100304
[10] A. Eustis, M.A. Henning, and A. Yeo, Independence in 5-uniform hypergraphs, Discrete Math. 339 (2016), no. 2, 1004–1027. https://doi.org/10.1016/j.disc.2015.10.034
[11] D.C. Fisher, P.A. McKenna, and E.D. Boyer, Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski’s graphs, Discrete Appl. Math. 84 (1998), no. 1-3, 93–105. https://doi.org/10.1016/S0166-218X(97)00126-1
[12] S.W. Golomb and L.R. Welch, Perfect codes in the lee metric and the packing of polyominoes, SIAM J. Appl. Math. 18 (1970), no. 2, 302–317.
[13] M. Goto and K.M. Kobayashi, Connected domination in grid graphs, arXiv preprint arXiv:2109.14108 (2021).
[14] S. Gravier and A. Khelladi, On the domination number of cross products of graphs, Discrete Math. 145 (1995), no. 1-3, 273–277. https://doi.org/10.1016/0012-365X(95)00091-A
[15] J.L. Gross and T.W. Tucker, Topological graph theory, Courier Corporation, 2001.
[16] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of domination in graphs, CRC press, 2013.
[17] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, vol. 64, Springer, 2020.
[18] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core concepts, Springer, 2023.
[19] S. Negami, The spherical genus and virtually planar graphs, Discrete Math. 70 (1988), no. 2, 159–168. https://doi.org/10.1016/0012-365X(88)90090-8
[20] S. Negami, Another approach to planar cover conjecture focusing on rotation systems, J. Math. Soc. Japan 76 (2024), no. 3, 975–996.
[21] B. Reed, Paths, stars and the number three, Combinatorics, Probability and Computing 5 (1996), no. 3, 277–295.
https://doi.org/10.1017/S0963548300002042
[22] D.P. Sumner, Critical concepts in domination, 86 (1991), no. 1-3, 33–46. https://doi.org/10.1016/0012-365X(90)90347-K
[23] Z. Tuza, Covering all cliques of a graph, Discrete Math. 86 (1990), no. 1-3, 117–126. https://doi.org/10.1016/0012-365X(90)90354-K
[24] V.V. Vazirani, Approximation algorithms, Springer Berlin Heidelberg, (2002).
[25] V.G. Vizing, Some unsolved problems in graph theory, Russian Mathematical Surveys 23 (1968), no. 6, 125–141.
https://doi.org/10.1070/RM1968v023n06ABEH001252
[26] H.B. Walikar, B.D. Acharya, and E. Sampathkumar, Recent developments in the theory of domination in graphs and its applications, 1979.
[27] M. Zwierzchowski, Domination parameters of a graph with added vertex, Opuscula Math. 24 (2004), no. 2, 231–234.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 15 February 2026

Files

Share

How to cite

Statistics