SDCTD sets in some products of graphs and its application

Articles in Press

Document Type : Original paper

Authors

School of Information Engineering, Tarim University, Alar, China

Abstract

This paper focuses on three types of product graphs, analyzing the relationships between their ECD sets, SDCTD sets, and factor graphs, while also constructing such ECD sets and SDCTD sets for the product graphs in question. We establish the necessary and sufficient conditions for an ECD set of a hypercube to be an SDCTD set, clarify the conditions under which an SDCTD set constitutes a PD set in a general graph $G$, and further deduce these conditions specifically for regular graphs and bipartite graphs. By hierarchically partitioning SDCTD sets via tree decomposition, we derive new upper bounds for the domination number of the modular product of two graphs, as well as for that of the modular product of two regular graphs. Additionally, we fully characterize all graph pairs $(G,H)$ for which $\gamma(G\diamond H)=5$ and prove a general lower bound  $\gamma(G\diamond G)\geq\gamma(G)+2$. The paper concludes by outlining several avenues for potential future research.

Keywords

Main Subjects

References

[1] S. Bermudo, I. Peterin, J. Sedlar, and R. Škrekovski, Domination number of modular product graphs, J. Comput. Appl. Math. 44 (2025), no. 2, Article number: 65.  https://doi.org/10.1007/s40314-024-03026-5
[2] B. Brešar, S. Klavžar, and D.F. Rall, Dominating direct products of graphs, Discrete Math. 307 (2007), no. 13, 1636–1642. https://doi.org/10.1016/j.disc.2006.09.013
[3] J.L. Gross, J. Yellen, and P. Zhang, Handbook of Graph Theory, second ed., Chapman & Hall/CRC, 2013.
[4] R.H. Hammack, W. Imrich,  and S. Klavžar, Handbook of Product Graphs, 2nd ed., CRC Press, Boca Raton, FL, 2011.
[5] Wilfried Imrich, Assoziative produkte von graphen, Österreichische Akademie der Wissenschaften Mathematisch-Naturwissenschaftliche Klasse. Sitzungsberichte. Abteilung II 180 (1972), 203–239 (German), (In German).
[6] C.X. Kang, A. Kelenc, I. Peterin, and E. Yi, On distance and strong metric dimension of the modular product, Bull. Malays. Math. Sci. Soc. 48 (2025), no. 1, Article number: 20. https://doi.org/10.1007/s40840-024-01800-6
[7] S. Klavžar and N. Seifter, Dominating cartesian products of cycles, Discrete Appl. Math. 59 (1995), no. 2, 129–136.
[8] J. Lee, Independent perfect domination sets in Cayley graphs, J. Graph Theory 37 (2001), no. 4, 213–219. https://doi.org/10.1002/jgt.1016
[9] G. Mekiš, Lower bounds for the domination number and the total domination number of direct product graphs, Discrete Math. 310 (2010), no. 23, 3310–3317. https://doi.org/10.1016/j.disc.2010.07.015
[10] R. Nowakowski and D. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996), no. 1, 53–79.
[11] Jian-Ping Ou, Domination numbers of strong products and lexicographic products of graphs, Journal of Wuyi University (2010), In Chinese. 
[12] Douglas F. Rall, Domination and packing in graph products, 20th Clemson Mini-Conference on Discrete Mathematics and Algorithms (Clemson, SC, USA), 2005.
[13] J. Sen and S.R. Kola, Broadcast domination of lexicographic and modular products of graphs, AKCE Int. J. Graphs Comb. 19 (2022), no. 3, 177–181. https://doi.org/10.1080/09728600.2022.2093145
[14] Z. Shao and R. Solis-Oba, $l(2, 1)$-labelings on the modular product of two graphs, Theor. Comput. Sci. 487 (2013), 74–81. https://doi.org/10.1016/j.tcs.2013.02.002
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 15 December 2025

Files

Share

How to cite

Statistics