آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,578 |
| تعداد مشاهده مقاله | 1,707,519 |
| تعداد دریافت فایل اصل مقاله | 1,590,793 |
New Characterization of Efficient Closed and Open Dominated Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 15، دوره 11، شماره 4، اسفند 2026، صفحه 1235-1247 اصل مقاله (415.2 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31349.2826 | ||
| نویسندگان | ||
| Veronica Hernandez Martinez1؛ Iztok Peterin* 2، 3 | ||
| 1Universidad Carlos III de Madrid, Madrid, Spain | ||
| 2Faculty of Electrical Engineering and Computer Science, University of Maribor, Slovenia | ||
| 3Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia | ||
| چکیده | ||
| 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). | ||
| کلیدواژهها | ||
| Efficient closed dominated graph؛ efficient open dominated graph؛ domination number؛ independence number؛ clique cover؛ Vizing conjecture | ||
| مراجع | ||
|
[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 | ||
|
آمار تعداد مشاهده مقاله: 155 تعداد دریافت فایل اصل مقاله: 83 |
||