In graph theory, a graph amalgamation is a relationship between two graphs (one graph is an amalgamation of another). Similar relationships include subgraphs and minors. Amalgamations can provide a way to reduce a graph to a simpler graph while keeping certain structure intact. The amalgamation can then be used to study properties of the original graph in an easier to understand context. Applications include embeddings,[1] computing genus distribution,[2] and Hamiltonian decompositions.
Let
G
H
G
H
H
G
\phi:E(G)\toE(H)
\psi:V(G)\toV(H)
x
y
G
\psi(x) ≠ \psi(y)
x
y
e
G
\psi(x)
\psi(y)
\phi(e)
H
e
x\inV(G)
\phi(e)
\psi(x)\inH
e
x,y\inV(G)
x ≠ y
\psi(x)=\psi(y)
\phi(e)
\psi(x)
Note that while
G
H
Edge colorings are invariant to amalgamation. This is obvious, as all of the edges between the two graphs are in bijection with each other. However, what may not be obvious, is that if
G
K2n+1
H
Figure 1 illustrates an amalgamation of
K5
\phi
\psi
v\inV(G) | \psi(v) | |
---|---|---|
v1 | u2 | |
v2 | u2 | |
v3 | u1 | |
v4 | u3 | |
v5 | u2 |
One of the ways in which amalgamations can be used is to find Hamiltonian Decompositions of complete graphs with 2n + 1 vertices.[4] The idea is to take a graph and produce an amalgamation of it which is edge colored in
n
K2n+1
In Hilton outlines a method for doing this, as well as a method for finding all Hamiltonian Decompositions without repetition. The methods rely on a theorem he provides which states (roughly) that if we have an outline Hamiltonian decomposition, we could have arrived at it by first starting with a Hamiltonian decomposition of the complete graph and then finding an amalgamation for it.