New Characterization of Efficient Closed and Open Dominated Graphs

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 Universidad Carlos III de Madrid, Madrid, Spain

2 Faculty of Electrical Engineering and Computer Science, University of Maribor, Slovenia

3 Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

Abstract

A graph $G$ is an efficient closed dominated graph (ECD-graph) if there exists a subset of vertices whose closed neighborhoods partition $V(G)$ and is an efficient open dominated graph (EOD-graph) if there exists a subset of vertices whose open neighborhoods partition $V(G)$. We present a new characterization of ECD- and EOD-graphs that involves independent number and a vertex clique cover of some family of cliques of closed neighborhood graph and open neighborhood graph, respectively, that are intersection graphs of closed and open neighborhoods, respectively. Several consequences are presented as well, one of them with respect to the Vizing's conjecture and the other solves a conjecture on EOD-graphs among toruses $C_t\Box C_r$ posed by Kuziak et al. (Discrete Math. Theoret. Comput. Sci. 16 (2014) 105-120).

Keywords

Main Subjects

References

[1] G. Abay-Asmerom, R.H. Hammack, and D.T. Taylor, Total perfect codes in tensor products of graphs, Ars Combin. 88 (2008), 129–134.
[2] G. Abay-Asmerom, R.H. Hammack, and D.T. Taylor, Perfect r-codes in strong products of graphs, Bull. Inst. Combin. Appl. 55 (2009), 66–72.
[3] B.D. Acharya and M.N. Vartak, Open neighbourhood graphs, Indian Institute of Technology Department of Mathematics Research Report 6 (1973).
[4] D.W. Bange, A.E. Barkauskas, and P.J. Slater, Efficient dominating sets in graphs, Appl. Discrete Math. 189 (1988), 189–199.
[5] A.M. Barcalkin and L.F. German, The external stability number of the cartesian product of graphs, Bul. Akad. Stiinte RSS Moldoven 1 (1979), no. 94, 5–8.
[6] N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973), no. 3, 289–296. https://doi.org/10.1016/0095-8956(73)90042-7
[7] A. Brandstädt, Efficient domination and efficient edge domination: A brief survey, Conference on Algorithms and Discrete Applied Mathematics, vol. 10743, Springer, 2018, pp. 1–14. https://doi.org/10.1007/978-3-319-74180-2_1
8] B. Brešar, P. Dorbec, W. Goddard, B.L. Hartnell, M.A. Henning, S. Klavžar, and D.F. Rall, Vizing’s conjecture: a survey and recent results, J. Graph Theory 69 (2012), no. 1, 46–76. https://doi.org/10.1002/jgt.20565
[9] T.T. Chelvam and S. Mutharasu, Efficient open domination in cayley graphs, Appl. Math. Lett. 25 (2012), no. 10, 1560–1564. https://doi.org/10.1016/j.aml.2011.12.036
[10] R. Cowen, S.H. Hechler, J.W. Kennedy, and A. Steinberg, Odd neighborhood transversals on grid graphs, Discrete Math. 307 (2007), no. 17-18, 2200–2208. https://doi.org/10.1016/j.disc.2006.11.006
[11] I.J. Dejter, Perfect domination in regular grid graphs, Australas. J. Combin. 42 (2008), 99–114.
[12] M.R. Fellows and M.N. Hoover, Perfect domination, Australas. J. Combin. 3 (1991), 141–150.
[13] H. Gavlas, K. Schultz, and P. Slater, Efficient open domination in graphs, Sci. Ser. A Math. Sci 6 (2003), 77–84.
[14] R.H. Hammack, W. Imrich, and S. Klavˇzar, Handbook of Product Graphs, vol. 2, CRC press Boca Raton, 2011.
[15] S. Klavžar, I. Peterin, and I.G. Yero, Graphs that are simultaneously efficient open domination and efficient closed domination graphs, Discrete Appl. Math. 217 (2017), 613–621. https://doi.org/10.1016/j.dam.2016.09.027
[16] S. Klavžar, S. Spacapan, and J. Žerovnik, An almost complete description of perfect codes in direct products of cycles, Adv. Appl. Math. 37 (2006), no. 1, 2–18. https://doi.org/10.1016/j.aam.2005.10.002
[17] W.F. Klostermeyer and E.M. Eschen, Perfect codes and independent dominating sets, Congr. Numer. 142 (2000), 7–28.
[18] W.F. Klostermeyer and J.L. Goldwasser, Total perfect codes in grid graphs, Bull. Inst. Combin. Appl. 46 (2006), 61–68.
[19] J. Kratochvíl and M. Křivánek, On the computational complexity of codes ingraphs, International Symposium on Mathematical Foundations of Computer Science, vol. 324, Springer, 1988, pp. 396–404.
https://doi.org/10.1007/BFb0017162
[20] J. Kratochvíl, P.D. Manuel, and M. Miller, Generalized domination in chordal graphs, Nordic J. Comput. 2 (1995), no. 1, 41–50.
[21] D. Kuziak, I. Peterin, and I.G. Yero, Efficient open domination in graph products, Discrete Math. Theor. Comput. Sci. 16 (2014), no. 1, 105–120. https://doi.org/10.46298/dmtcs.1267
[22] I.H. Ladinek and J. Žerovnik, Perfect codes in direct graph bundles, Inform. Process. Lett. 115 (2015), no. 9, 707–711. https://doi.org/10.1016/j.ipl.2015.03.010
[23] A.A. McRae, Generalizing NP-Completeness Proofs for Bipartite Graphs and Chordal Graphs, Clemson University, 1994.
[24] M. Milanič, Hereditary efficiently dominatable graphs, J. Graph Theory 73 (2013), no. 4, 400–424.
https://doi.org/10.1002/jgt.21685
[25] M. Mollard, On perfect codes in cartesian products of graphs, European J. Combin. 32 (2011), no. 3, 398–403.
https://doi.org/10.1016/j.ejc.2010.11.007
[26] A. Mukhopadhyay, The square root of a graph, J. Combin. Theory 2 (1967), no. 3, 290–295. https://doi.org/10.1016/S0021-9800(67)80030-9
[27] C.B. Smart and P.J. Slater, Complexity results for closed neighborhood order parameters, Congr. Numer. 112 (1995), 83–96.
[28] M. Sonntag and H.-M. Teichert, Neighborhood structures and products of undirected graphs, Discrete Math. 313 (2013), no. 4, 563–574. https://doi.org/10.1016/j.disc.2012.11.028
[29] T.K. Šumenjak, I. Peterin, D.F. Rall, and A. Tepeh, Partitioning the vertex set of $G$ to make $G\Box H$ an efficient open domination graph, Discrete Math. Theor. Comput. Sci. 18 (2016), no. 3, #10. https://doi.org/10.46298/dmtcs.1277
[30] D.T. Taylor, Perfect r-codes in lexicographic products of graphs, Ars Combin. 93 (2009), 215–223.
[31] P.M. Weichsel, The Kronecker product of graphs, Proceedings of the American mathematical society 13 (1962), no. 1, 47–52.
[32] J. Žerovnik, Perfect codes in direct products of cycles–A complete characterization, Adv. Appl. Math. 41 (2008), no. 2, 197–205. https://doi.org/10.1016/j.aam.2007.04.006
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 05 June 2026

Files

Share

How to cite

Statistics