WOLFRAM

Wolfram Language & System Documentation Center

GraphProduct[g1,g2]

gives the Cartesian product of the graphs g1 and g2.

GraphProduct[g1,g2,"op"]

gives the product of type "op" for the graphs g1 and g2

Details and Options
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Directed Graphs  
Undirected Graphs  
Mixed Graphs  
Multigraphs  
Weighted Graphs  
Special Graphs  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

GraphProduct

GraphProduct[g1,g2]

gives the Cartesian product of the graphs g1 and g2.

GraphProduct[g1,g2,"op"]

gives the product of type "op" for the graphs g1 and g2

Details and Options

  • GraphProduct is also known as box product.
  • GraphProduct is typically used to produce new graphs from Boolean combinations of initial graphs.
  • GraphProduct[g1,g2] gives a graph with vertices formed from the Cartesian product of the vertices of g1 and vertices of g2. The vertices {u1,u2} and {v1,v2} are connected if u1v1 and u2 is connected to v2, or u2v2 and u1 is connected to v1.
  • GraphProduct[g1,g2,"op"] gives a graph product of type "op" with edges {u1,u2}{v1,v2} subject to the following conditions:
  • "Cartesian"(u1v1 ∧ u2v2)∨(u2v2∧u1v1)
    "Conormal"(u1v1)∨(u2v2)
    "Lexicographical"(u1v1)∨(u1v1∧u2v2)
    "Normal"(u1v1∧u2v2)∨(u2v2∧u1v1)∨(u1v1∧u2v2)
    "Rooted"(u1v1 ∧ u2v2)∨(u1v1 ∧ u2v2r)
    "Tensor"(u1v1)∧(u2v2)
  • The vertex r is the first vertex in VertexList[g2].
  • GraphProduct[g1,g2] is effectively equivalent to GraphProduct[g1,g2,"Cartesian"].
  • GraphProduct works with undirected graphs, directed graphs, multigraphs and mixed graphs.

Examples

open all close all

Basic Examples  (3)

Cartesian product of two graphs:

Wolfram Language code: GraphProduct[[image], [image]]

A table of graph products:

Wolfram Language code: Table[GraphProduct[[image], [image], op, Rule[...]], {op, {...}}]

Generate grid graphs:

Wolfram Language code: GraphProduct[PathGraph[{1, 2, 3}], PathGraph[{1, 2, 3, 4}], GraphLayout -> "GridEmbedding"]

Torus graphs:

Wolfram Language code: GraphProduct[CycleGraph[10], CycleGraph[6], GraphLayout -> "SpringElectricalEmbedding"]

Scope  (30)

Directed Graphs  (5)

GraphProduct works with directed graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Simple directed graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Directed multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Directed weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Directed annotated graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Undirected Graphs  (5)

GraphProduct works with undirected graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Simple undirected graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Undirected multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Undirected weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Undirected annotated graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Mixed Graphs  (5)

GraphProduct works with mixed graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Simple mixed graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Mixed multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Mixed weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Mixed annotated graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Multigraphs  (5)

GraphProduct works with multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Directed multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Mixed multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Weighted multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Annotated multigraphs:

Wolfram Language code: GraphProduct[[image], [image]]

Weighted Graphs  (5)

GraphProduct works with weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Directed weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Undirected weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Mixed weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Annotated weighted graphs:

Wolfram Language code: GraphProduct[[image], [image]]

Special Graphs  (5)

GraphProduct works on entity graphs:

Wolfram Language code: GraphProduct[["petersen graph"], ["petersen graph"]]

GraphProduct works on trees:

Wolfram Language code: GraphProduct[[image], [image]]

Use rules to specify the graph:

Wolfram Language code: GraphProduct[{1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1}, {1 -> 2}]

GraphProduct works with more than two graphs:

Wolfram Language code: GraphProduct[[image], [image], [image]]

Generate a list of different graph products:

Wolfram Language code: {g, h} = {[image], [image]};
Wolfram Language code: Table[GraphProduct[g, h, type], {type, {"Cartesian", "Tensor", "Lexicographical", "Normal", "Conormal", "Rooted"}}]

Properties & Relations  (6)

For two graphs with vi vertices, the number of vertices of their product is v1 v2 :

Wolfram Language code: g = [image]; h = [image];
Wolfram Language code: VertexCount[GraphProduct[g, h]] == VertexCount[g] * VertexCount[h]

For two undirected graphs with vi vertices and ei edges, the number of edges of the Cartesian product is v1 e2+v2 e1:

Wolfram Language code: g = [image]; h = [image];
Wolfram Language code: {v1, v2} = VertexCount /@ {g, h};
Wolfram Language code: {e1, e2} = EdgeCount /@ {g, h};
Wolfram Language code: EdgeCount@GraphProduct[g, h, "Cartesian"] == v1 * e2 + v2 * e1

Tensor product is 2 e1e2:

Wolfram Language code: EdgeCount@GraphProduct[g, h, "Tensor"] == 2e1 e2

Lexicographical product is v1 e2+ e1v22 :

Wolfram Language code: EdgeCount@GraphProduct[g, h, "Lexicographical"] == v1 * e2 + e1 * v2 ^ 2

Normal product is v1 e2+v2 e1 + 2 e1e2:

Wolfram Language code: EdgeCount@GraphProduct[g, h, "Normal"] == v1 * e2 + v2 * e1 + 2e1 e2

Co-normal product is v12 e2+ e1v22 - 2e1e2:

Wolfram Language code: EdgeCount@GraphProduct[g, h, "Conormal"] == v1 ^ 2 * e2 + e1 * v2 ^ 2 - 2e1 e2

Rooted product is v1 e2+ e1:

Wolfram Language code: EdgeCount@GraphProduct[g, h, "Rooted"] == v1 * e2 + e1

The Cartesian product of two single edges is a cycle:

Wolfram Language code: GraphProduct[[image], [image], "Cartesian"]

The normal product of two single edges is a complete graph:

Wolfram Language code: GraphProduct[[image], [image], "Normal"]

The tensor product of two single edges is a cross:

Wolfram Language code: GraphProduct[[image], [image], "Tensor"]

TorusGraph[{m,n}] is the graph formed from the Cartesian product of the cycle graphs and :

Wolfram Language code: g = TorusGraph[{10, 6}]
Wolfram Language code: h = GraphProduct[CycleGraph[10], CycleGraph[6]]
Wolfram Language code: IsomorphicGraphQ[g, h]
Wolfram Research (2022), GraphProduct, Wolfram Language function, https://reference.wolfram.com/language/ref/GraphProduct.html.

Text

Wolfram Research (2022), GraphProduct, Wolfram Language function, https://reference.wolfram.com/language/ref/GraphProduct.html.

CMS

Wolfram Language. 2022. "GraphProduct." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/GraphProduct.html.

APA

Wolfram Language. (2022). GraphProduct. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/GraphProduct.html

BibTeX

@misc{reference.wolfram_2026_graphproduct, author="Wolfram Research", title="{GraphProduct}", year="2022", howpublished="\url{https://reference.wolfram.com/language/ref/GraphProduct.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_graphproduct, organization={Wolfram Research}, title={GraphProduct}, year={2022}, url={https://reference.wolfram.com/language/ref/GraphProduct.html}, note=[Accessed: 13-June-2026]}