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) ∪V(H), and edge-set E(G) ∪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 x H of G and H. The product has vertex-set V(G) x V(H). Two vertices u = (u₁, u₂) and v = (v₁, v₂) of K are adjacent when either

(a)

u₁ = v₁ and u₂ adj v₂, or

(b)

u₂ = v₂ and u₁ adj v₁.

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) x V(H). Two vertices u = (u₁, u₂) and v = (v₁, v₂) of K are adjacent when either

(a)

u₁ adj v₁, or

(b)

u₁ = v₁ and u₂ adj v₂.

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) x V(H). Two vertices u = (u₁, u₂) and v = (v₁, v₂) of K are adjacent when u₁ adj v₁ and u₂ adj v₂.

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.