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).
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 Klavar, 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.Sabidussi,
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.