# 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 u1==v1 and u2 is connected to v2, or u2==v2 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" (u1==v1 ∧ u2v2)∨(u2==v2∧u1v1) "Conormal" (u1v1)∨(u2v2) "Lexicographical" (u1v1)∨(u1==v1∧u2v2) "Normal" (u1==v1∧u2v2)∨(u2==v2∧u1v1)∨(u1v1∧u2v2) "Rooted" (u1==v1 ∧ u2v2)∨(u1v1 ∧ u2==v2==r) "Tensor" (u1v1)∧(u2v2)
• 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 allclose all

## Basic Examples(3)

Cartesian product of two graphs:

A table of graph products:

Generate grid graphs:

Torus graphs:

## Scope(30)

### Directed Graphs(5)

GraphProduct works with directed graphs:

Simple directed graphs:

Directed multigraphs:

Directed weighted graphs:

Directed annotated graphs:

### Undirected Graphs(5)

GraphProduct works with undirected graphs:

Simple undirected graphs:

Undirected multigraphs:

Undirected weighted graphs:

Undirected annotated graphs:

### Mixed Graphs(5)

GraphProduct works with mixed graphs:

Simple mixed graphs:

Mixed multigraphs:

Mixed weighted graphs:

Mixed annotated graphs:

### Multigraphs(5)

GraphProduct works with multigraphs:

Directed multigraphs:

Mixed multigraphs:

Weighted multigraphs:

Annotated multigraphs:

### Weighted Graphs(5)

GraphProduct works with weighted graphs:

Directed weighted graphs:

Undirected weighted graphs:

Mixed weighted graphs:

Annotated weighted graphs:

### Special Graphs(5)

GraphProduct works on entity graphs:

GraphProduct works on trees:

Use rules to specify the graph:

GraphProduct works with more than two graphs:

Generate a list of different graph products:

## Properties & Relations(6)

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

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

Tensor product is 2 e1e2:

Lexicographical product is v1 e2+ e1v22 :

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

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

Rooted product is v1 e2+ e1:

The Cartesian product of two single edges is a cycle:

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

The tensor product of two single edges is a cross:

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