# graphComposition -- A method for composing two graphs

## Synopsis

• Usage:
F = graphComposition(G,H)
• Inputs:
• G, an instance of the type Graph,
• H, an instance of the type Graph,
• Outputs:
• F, an instance of the type Graph, The Graph Composition of G and H

## 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