Macaulay2 » Documentation
Packages » Graphs :: graphComposition
next | previous | forward | backward | up | index | toc

graphComposition -- A method for composing two graphs

Synopsis

Description

This method will take in any two graphs and output the composition of the two graphs. The vertex set of the graph composition of G and H is the cartesian product of the vertex sets of G and H. The keys for each vertex will be output as a sequence to represent this. The edge set is formed by the rule that any two vertices (u,v) and (x,y) are adjacent the composition of G and H if and only if either u is adjacent with x in G or u = x and v is adjacent with y in H. Be careful, since this operation is not commutative, and the user needs to be mindful what order the graphs are entered into the method.

i1 : G = graph({1,2},{{1,2}});
 
i2 : H = graph({3,4,5},{{3,4},{4,5}})

o2 = Graph{3 => {4}   }
           4 => {3, 5}
           5 => {4}

o2 : Graph
 
i3 : GH = graphComposition(G,H)

o3 = Graph{(1, 3) => {(2, 5), (2, 3), (1, 4), (2, 4)}        }
           (1, 4) => {(2, 5), (1, 3), (2, 3), (2, 4), (1, 5)}
           (1, 5) => {(2, 5), (2, 3), (1, 4), (2, 4)}
           (2, 3) => {(1, 3), (1, 4), (2, 4), (1, 5)}
           (2, 4) => {(2, 5), (1, 3), (2, 3), (1, 4), (1, 5)}
           (2, 5) => {(1, 3), (1, 4), (2, 4), (1, 5)}

o3 : Graph
 
i4 : HG = graphComposition(H,G)

o4 = Graph{(3, 1) => {(3, 2), (4, 1), (4, 2)}                }
           (3, 2) => {(3, 1), (4, 1), (4, 2)}
           (4, 1) => {(5, 2), (3, 1), (3, 2), (4, 2), (5, 1)}
           (4, 2) => {(5, 2), (3, 1), (3, 2), (4, 1), (5, 1)}
           (5, 1) => {(5, 2), (4, 1), (4, 2)}
           (5, 2) => {(4, 1), (4, 2), (5, 1)}

o4 : Graph

See also

Ways to use graphComposition :

For the programmer

The object graphComposition is a method function.