# Unions and Products of Graphs

The support and vertex/edge decorations of the original graphs are *not* retained in the graph resulting from applying any of the union functions below.

## `Union(G, H): GrphUnd, GrphUnd -> GrphUnd`

## `Union(G, H): GrphDir, GrphDir -> GrphDir`

## `G join H: GrphDir, GrphDir -> GrphDir`

## `G join H: GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex sets $V(G)$ and $V(H)$, respectively, construct their union, i.e. the graph with vertex-set $V(G) \cup V(H)$, and edge-set $E(G) \cup E(H)$.

## `EdgeUnion(G, H): GrphDir, GrphDir -> GrphDir`

## `EdgeUnion(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ having the same number of vertices, construct their edge union $K$. This construction identifies the $i$-th vertex of $G$ with the $i$-th vertex of $H$ for all $i$. The edge union has the same vertex-set as $G$ (and hence as $H$) and vertices $u$ and $v$ of $K$ are adjacent if and only if either $u$ and $v$ are adjacent in $G$ or $u$ and $v$ are adjacent in $H$.

## `CompleteUnion(G, H): GrphDir, GrphDir -> GrphDir`

## `CompleteUnion(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, construct the complete union of $G$ and $H$. This graph consists of the union of $G$ and $H$ (`Union(G, H)`), together with edges $uv$, for all $u$ in $V(G)$ and all $v$ in $V(H)$.

## `CartesianProduct(G, H): GrphDir, GrphDir -> GrphDir`

## `CartesianProduct(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, form the product $K = G\times H$ of $G$ and $H$. The product has vertex-set $V(G)\times V(H)$. Two vertices $u = (u_1, u_2)$ and $v = (v_1, v_2)$ of $K$ are adjacent when either

**(a)**
$u_1 = v_1$ and $u_2\ {\operatorname{adj}}v_2$, or

**(b)**
$u_2 = v_2$ and $u_1\ {\operatorname{adj}}v_1$.

## `LexProduct(G, H): GrphDir, GrphDir -> GrphDir`

## `LexProduct(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, form the lexicographic product $K$ of $G$ and $H$. The lexicographic product has vertex-set $V(G)\times V(H)$. Two vertices $u = (u_1, u_2)$ and $v = (v_1, v_2)$ of $K$ are adjacent when either

**(a)**
$u_1\ {\operatorname{adj}}v_1$, or

**(b)**
$u_1 = v_1$ and $u_2\ {\operatorname{adj}}v_2$.

## `TensorProduct(G, H): GrphDir, GrphDir -> GrphDir`

## `TensorProduct(G, H): GrphUnd, GrphUnd -> GrphUnd`

Given graphs $G$ and $H$ with disjoint vertex-sets $V(G)$ and $V(H)$, respectively, form the tensor product $K$ of $G$ and $H$. This graph has vertex-set $V(G)\times V(H)$. Two vertices $u = (u_1, u_2)$ and $v = (v_1, v_2)$ of $K$ are adjacent when $u_1\ {\operatorname{adj}}v_1$ and $u_2\ {\operatorname{adj}}v_2$.

## `G ^ n: GrphUnd, RngIntElt -> GrphUnd`

Given a graph $G$ and a positive integer $n$, construct the $n$-th power $K$ of $G$. This graph has the same vertex-set as $G$, and vertices $u$ and $v$ of $K$ are adjacent if and only if the distance between $u$ and $v$ in $G$ is less than or equal to $n$.