TOPICS

# 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

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

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

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 following table gives examples of some graph Cartesian products. Here, denotes a cycle graph, a complete graph, a path graph, and a star graph.

Book Graph, Circulant Graph, Crown Graph, Graph Composition, Graph Dimension, Graph Product, Grid Graph, Ladder Graph, Median Graph, Prism Graph, Rook Complement Graph, Rook Graph, Stacked Book Graph, Torus Grid Graph, Unit-Distance Graph, Vizing Conjecture

Portions of this entry contributed by Lorenzo Sauras-Altuzarra

## Explore with Wolfram|Alpha

More things to try:

## References

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. Combinatorics 7, 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." Mathematika 12, 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.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. Sistemy 9, 30-43, 1963.

## Referenced on Wolfram|Alpha

Graph Cartesian Product

## Cite this as:

Sauras-Altuzarra, Lorenzo and Weisstein, Eric W. "Graph Cartesian Product." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphCartesianProduct.html