[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Unions and Products of Graphs
Unions and Products of Graphs
Subsections
Union(G, H) : GrphDir, GrphDir -> GrphDir
Union(G, H) : GrphUnd, GrphUnd -> GrphUnd
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) union V(H), and edge set E(G) union 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_1, u_2) and
v = (v_1, v_2) of K are adjacent when either
- u_1 = v_1 and u_2 adj v_2, or
- u_2 = v_2 and u_1 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) x V(H). Two vertices
u = (u_1, u_2) and v = (v_1, v_2) of K are adjacent when either
- u_1 adj v_1, or
- u_1 = v_1 and u_2 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) x V(H). Two vertices u = (u_1, u_2) and
v = (v_1, v_2) of K are adjacent when u_1 adj v_1 and
u_2 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.
Converting between Graphs and Digraphs
OrientatedGraph(G) : GrphUnd -> GrphDir
Given a graph G, produce a digraph D whose vertex set is the same as
that of G and whose edge set consists of the edges of G, each given
an arbitary direction. The edges of D are always directed from the
lower numbered vertex to the higher numbered vertex. Thus, if G
contains the edge { i, j }, then D will have the edge
[i, j] if i < j, otherwise the edge [j, i].
UnderlyingGraph(D) : GrphDir -> GrphUnd
The underlying graph G of the digraph D. Thus, G has the same
vertex set as D, and two vertices u and v are adjacent in G
if and only if, in D, there is either an edge directed from u to
v or from v to u.
UnderlyingDigraph(G) : GrphUnd -> GrphDir
The underlying digraph D of the graph G. Thus, D has the same
vertex set as G, and if vertices u and v are adjacent in G
then in D, there will be both an edge directed from u to v and
an edge directed from v to u.
[Next] [Prev] [Right] [Left] [Up] [Index] [Root]