Exact double domination in subdivision‎, Mycielskian and ‎middle graphs

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Faculty of Science, Imam Khomeini International University, PO Box: 34148 - 96818, Qazvin, Iran

Abstract

An exact doubly dominating set (also called an efficient doubly dominating set in [F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201–213]) for a graph G=(V,E) is a subset D of vertices such that each vertex of G is dominated by exactly two vertices of D. In this paper we  show that subdivision graphs admit exact doubly dominating sets under specific conditions, while Mycielskian and middle graphs do not. We provide some characterizations and we investigate  the existence of exact doubly dominating sets  for their complements.

Keywords

Main Subjects

References

[1] S. Ahmadi, E. Vatandoost, and A. Behtoei, Domination number and identifying code number of the subdivision graphs, J. Algebraic Syst. 13 (2025), no. 2, 1–11.  https://doi.org/10.22044/jas.2023.12257.1649
[2] D.W. Bange, A.E. Barkauskas, and P.J. Slater, Efficient dominating sets in graphs, SIAM, Philadelphia, PA, 1988.
[3] N. Biggs, Perfect codes in graphs, J. Combin. Theory (B) 15 (1973), no. 3, 289–296. https://doi.org/10.1016/0095-8956(73)90042-7
[4] B. Chaluvaraju, M. Chellali, and K.A. Vidya, Perfect codes in graphs, Australas. J. Comb. 48 (2010), 175–184.
[5] M. Chellali, A. Khelladi, and F. Maffray, Exact double domination in graph, Discuss. Math. Graph Theory 25 (2005), no. 3, 291–302.
[6] E.J. Cockayne, B. L. Hartnell, S.T. Hedetniemi, and R. Laskar, Perfect domination in graphs, J. Combin. Inform. System Sci. 18 (1993), 136–148.
[7] M.R. Fellows and M.N. Hoover, Perfect domination, Australas J. Comb. 3 (1991), 141–150.
[8] J.F. Fink and M.S. Jacobson, n-domination in graphs, Graph Theory with Appl. to Algorithms and Comp. Sci. (Y. Alavi, G. Chartrand, D.R. Lick, C.E. Wall, and L. Lesniak, eds.), John Wiley & Sons, Inc., United States, 1985, pp. 283–300.
[9] A. Ghalavand, S. Klavžar, M. Tavakoli, and I.G. Yero, On mixed metric dimension in subdivision, middle and total graphs, Quaestiones Math. 46 (2023), no. 12, 2517–2527.  https://doi.org/10.2989/16073606.2023.2169206
[10] T. Hamada and I. Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Math. 14 (1976), no. 3, 247–255.  https://doi.org/10.1016/0012-365X(76)90037-6
[11] F. Harary and T.W. Haynes, Nordhaus-Gaddum inequalities for domination in graphs, Discrete Mathe. 155 (1996), no. 1-3, 99–105.  https://doi.org/10.1016/0012-365X(94)00373-Q
[12]  F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201–213.
[13] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, CRC Press, New York, 1998.
[14] F. Kazemnejad, B. Pahlavsay, E. Palezzato, and M. Torielli, Domination number of middle graphs, Trans. Comb. 12 (2023), no. 2, 79–91.
[15] R. Khoeilar, M. Kheibari, Z. Shao, and S.M. Sheikholeslami, Total k-rainbow domination subdivision number in graphs, Computer Sci. J. Moldova 28 (2020), no. 2, 152–169.
[16] R.Y. Salkhori, E. Vatandoost, and A. Behtoei, 2-rainbow domination number of the subdivision of graphs, Commun. Comb. Optim. to appear (2025), https://doi.org/10.22049/cco.2024.28850.1749
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 02 May 2025

Files

Share

How to cite

Statistics