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

graphComposition -- A method for composing two graphs

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:

  • graphComposition(Graph,Graph)

For the programmer

The object graphComposition is a method function.


The source of this document is in /build/reproducible-path/macaulay2-1.25.05+ds/M2/Macaulay2/packages/Graphs.m2:4865:0.