On primality of Cartesian product of graphs

Purpose The present work focuses on the primality and the Cartesian product of graphs. Design/methodology/approach Given a graph G, a subset M of V (G) is a module of G if, for a, b ∈ M and x ∈ V (G) \ M, xa ∈ E(G) if and only if xb ∈ E(G). A graph G with at least three vertices is prime if the empty set, the single-vertex sets and V (G) are the only modules of G. Findings Motivated by works obtained on “the Cartesian product of graphs” and “the primality,” this paper creates a link between the two notions. Originality/value In fact, we study the primality of the Cartesian product of two connected graphs minus k vertices, where k ∈ {0, 1, 2}.