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).
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).
Buckley, F. and Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin.4, 23-30, 1988.Beineke,
L. W. and Wilson, R. J. (Eds.). Topics
in Algebraic Graph Theory. New York: Cambridge University Press, p. 104,
2004.Clark, W. E. and Suen, S. "An Inequality Related to Vizing's
Conjecture." Electronic J. Combinatorics7, No. 1, N4, 1-3,
2000. http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html.Erdős,
P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika12,
118-122, 1965.Hammack, R.; Imrich, W.; and Klavžar, S. Handbook
of Product Graphs, 2nd ed. Boca Raton, FL: CRC Press, 2016.Harary,
F. Graph
Theory. Reading, MA: Addison-Wesley, 1994.Hartnell, B. and Rall,
D. "Domination in Cartesian Products: Vizing's Conjecture." In Domination
in Graphs--Advanced Topics (Ed. T. W. Haynes, S. T. Hedetniemi,
and P. J. Slater). New York: Dekker, pp. 163-189, 1998.Imrich,
W. "Kartesisches Produkt von Mengensystemen und Graphen." Studia Sci.
Math. Hungar.2, 285-290, 1967.Imrich, W.; Klavzar, S.; and
Rall, D. F. Graphs
and their Cartesian Product. Wellesley, MA: A K Peters, 2008.Obata,
N. "Complete Multipartite Graphs of Non-QE Class." 12 Jun 2022. https://arxiv.org/abs/2206.05848.ObataSabidussi,
G. "Graph Multiplication." Math. Z.72, 446-457, 1960.Salazar,
G. and Ugalde, E. "An Improved Bound for the Crossing Number of : A Self-Contained Proof Using Mostly Combinatorial
Arguments." Graphs Combin.20, 247-253, 2004.Skiena,
S. "Products of Graphs." §4.1.4 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 133-135, 1990.Vizing, V. G. "The
Cartesian Product of Graphs." Vyčisl. Sistemy9, 30-43, 1963.
, 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 ![[u_1=v_1 and u_2 adj v_2]](/images/equations/GraphCartesianProduct/Inline12.svg)
or ![[u_2=v_2 and u_1 adj v_1]](/images/equations/GraphCartesianProduct/Inline13.svg)
(Harary 1994, p. 22).
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
denotes the Kronecker product (Hammack et
al. 2016).
and 
, their graph Cartesian product has
denotes vertex count and 
denotes edge count.
denotes a cycle graph, 
a complete graph, 
a path graph, 
a star graph, 
the Shrikhande graph,
and 
a Hamming graph.
with 
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).
, 
, ..., each having two or more vertices, is 
(Obata 2022).
: A Self-Contained Proof Using Mostly Combinatorial
Arguments." Graphs Combin. 20, 247-253, 2004.Skiena,
S. "Products of Graphs." §4.1.4 in