On subgraph relationships between graph products

Abstract

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.