Graph Cartesian Product

The Cartesian graph product , also called the graph box product and sometimes simply known as "the" graph product (Beineke and Wilson 2004, p. 104) and sometimes denoted (e.g., Salazar and Ugalde 2004; though this notation is more commonly used for the distinct graph tensor product) of graphs and with disjoint point sets and and edge sets and is the graph with point set and adjacent with whenever or (Harary 1994, p. 22).

Letting denote the adjacency matrix, the identity matrix, and the vertex count of , the adjacency matrix of the graph Cartesian product of simple graphs and is given by

(1)

where denotes the Kronecker product (Hammack et al. 2016).

Graph Cartesian products can be computed in the Wolfram Language using GraphProduct[G1, G2, "Cartesian"].

Given two graphs and , their graph Cartesian product has

(2)

vertices and

(3)

edges, where denotes vertex count and denotes edge count.

The following table gives examples of some graph Cartesian products. Here, denotes a cycle graph, a complete graph, a path graph, a star graph, the Shrikhande graph, and a Hamming graph.

product	result
	grid graph
	ladder graph
	grid graph
	prism graph
	stacked prism graph
	torus grid graph
with	circulant graph
	book graph
	stacked book graph
	crown graph
	KC graph
	KP graph
	rook graph
	rook complement graph
	Hamming graph
	hypercube graph
	Doob graph

If is a unit-distance graph, then so is . More generally, a simple relationship exists between the graph dimension of and that of (Erdős et al. 1965, Buckley and Harary 1988).

The quadratic embedding constant of a graph Cartesian product of graphs , , ..., each having two or more vertices, is (Obata 2022).

Let and be nontrivial simple graphs that are connected, and suppose is 3-connected. Then admits a torus graph embedding iff is an outer-cylindrical graph and (Badgett et al. 2026).