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.
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).
See alsoBook Graph,
Circulant Graph,
Crown Graph,
Graph Composition,
Graph Dimension,
Graph Product,
Grid Graph,
Hamming Graph,
KC Graph,
KP Graph,
Ladder Graph,
Median Graph,
Prism Graph,
Rook Complement Graph,
Rook Graph,
Stacked Book Graph,
Stacked Prism Graph,
Torus Grid Graph,
Unit-Distance Graph,
Vizing ConjecturePortions of this entry contributed by Lorenzo Sauras-Altuzarra
Explore with Wolfram|Alpha ReferencesBuckley, 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.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. Sistemy 9, 30-43, 1963. Referenced on Wolfram|AlphaGraph Cartesian Product Cite this as:Sauras-Altuzarra, Lorenzo and Weisstein, Eric W. "Graph Cartesian Product." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphCartesianProduct.html
Subject classificationsRetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4