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\).