Connectivity and other invariants of generalized products of graphs

Original · EN

Figueroa-Centeno et al. introduced the following product of digraphs: let D be a digraph and let Γ be a family of digraphs such that V(F)=V for every F∈ Γ. Consider any function h:E(D)Γ. Then the product D⊗ₕ Γ is the digraph with vertex set V(D)× V and ((a,x),(b,y))∈ E(D⊗ₕΓ) if and only if (a,b)∈ E(D) and (x,y)∈ E(h (a,b)). In this paper, we introduce the undirected version of the ⊗ₕ-product, which is a generalization of the classical direct product of graphs and, motivated by it, we also recover a generalization of the classical lexicographic product of graphs that was introduced by Sabidussi en 1961. We study connectivity properties and other invariants in terms of the factors. We also present a new intersection graph that emerges when we characterize the connectivity of ⊗ₕ-product of graphs.