On subgraph relationships between graph products
Keywords:
Array, Array, Array, Array, ArrayAbstract
Graph products play an important role in graph theory by providing systematic methods for constructing complex graphs from simpler ones and by revealing structural relationships among different graph classes. In this paper, we investigate subgraph relations among several standard graph products, including the Cartesian, lexicographic, tensor, modular, co-normal, strong, homomorphic, and rooted products. By comparing their defining adjacency conditions, we establish a collection of inclusion results between these products. In particular, we prove that the Cartesian product is a subgraph of the lexicographic, co-normal, and strong products, while the lexicographic product is itself a subgraph of the co-normal product. We further show that the tensor product is a subgraph of the lexicographic, modular, strong, and co-normal products. In addition, the strong product is shown to be a subgraph of both the lexicographic and co-normal products. Finally, we establish that the rooted product forms a subgraph of the Cartesian, lexicographic, co-normal, and strong products. Illustrative examples are included to visualise these relationships. The results obtained provide a clearer understanding of the structural hierarchy among graph product operations and may support further investigations in algebraic graph theory and network modelling.
References
[1] G. Chartrand, L. Lesniak & P. Zhang, Graphs & digraphs, 5th ed., CRC Press, Boca Raton, FL, USA, 2010. https://doi.org/10.1201/b14892.
[2] B. George, J. Jose & R. K. Thumbakara, On some properties of modular and homomorphic products of graphs, in Advances in Algebra, Analysis and Topology, S. Singh, K. Chakraborty, B. Kour & S. Kaur (Eds.), CRC Press, Boca Raton, FL, USA, 2024, pp. 52--60. https://doi.org/10.1201/9781032634142-6.
[3] R. Hammack, W. Imrich & S. Klav{v z}ar, Handbook of product graphs, 2nd ed., CRC Press, Boca Raton, FL, USA, 2011. https://doi.org/10.1201/b10959.
[4] D. Bozovic & I. Peterin, ``Efficient open domination in digraph products'', Mathematics 8 (2020) 496. https://doi.org/10.3390/math8040496.
[5] M. Changat, P. G. Narasimha-Shenoi, M. S. T. Joseph & B. S. Anand, ``Boundary-type sets of strong product of directed graphs'', Ars Mathematica Contemporanea 20 (2021) 275. https://doi.org/10.26493/1855-3974.2229.5f1.
[6] J. Feigenbaum, ``Directed Cartesian-product graphs have unique factorizations that can be computed in polynomial time'', Discrete Applied Mathematics 15 (1986) 105. https://doi.org/10.1016/0166-218X(86)90023-5.
[7] K. Manion, A lexicographic product cancellation property for digraphs, M.S. thesis, Virginia Commonwealth University, Richmond, VA, USA, 2012. Available online: https://scholarscompass.vcu.edu/etd/2932/.
[8] P. Poto{v c}nik & S. Wilson, ``The separated box product of two digraphs'', European Journal of Combinatorics 62 (2017) 35. https://doi.org/10.1016/j.ejc.2016.11.007.
[9] B. George, J. Jose & R. K. Thumbakara, ``Vertex and arc counts in Cartesian, lexicographic and strong products of digraphs'', Proceedings of the Fifth International Conference on Emerging Trends in Mathematical Sciences & Computing, Springer, Cham, Switzerland, 2024, pp. 93--103. https://doi.org/10.1007/978-3-031-71125-1_8.
[10] J. Jose, R. K. Thumbakara, S. P. George & B. George, ``Expanding graph theory: Product operations and properties in directed graph contexts'', IAENG International Journal of Applied Mathematics 54 (2024) 2691. Available online: https://www.iaeng.org/IJAM/issues_v54/issue_12/IJAM_54_12_19.pdf.
Published
How to Cite
Issue
Section
Copyright (c) 2026 Jinta Jose, Ninu S. Lal, Bobin George (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
