Graph Cartesian Product


The Cartesian graph product G=G_1 square G_2, also called the graph box product and sometimes simply known as "the" graph product (Beineke and Wilson 2004, p. 104) and sometimes denoted G_1×G_2 (e.g., Salazar and Ugalde 2004; though this notation is more commonly used for the distinct graph tensor product) of graphs G_1 and G_2 with disjoint point sets V_1 and V_2 and edge sets X_1 and X_2 is the graph with point set V_1×V_2 and u=(u_1,u_2) adjacent with v=(v_1,v_2) whenever [u_1=v_1 and u_2 adj v_2] or [u_2=v_2 and u_1 adj v_1] (Harary 1994, p. 22).

Letting A(G) denote the adjacency matrix, I_n the n×n identity matrix, and |V(G)| the vertex count of G, the adjacency matrix of the graph Cartesian product of simple graphs G and H is given by

 A(G square H)=A(G) tensor I_(|V(H)|)+I_(|V(G)|) tensor A(H),

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

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

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

The following table gives examples of some graph Cartesian products. Here, C_n denotes a cycle graph, K_n a complete graph, P_n a path graph, and S_n a star graph.

See also

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


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.ő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 C_m×C_n: 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.

Subject classifications