Graph amalgamation

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.

Edge colorings are invariant to amalgamation.

This is obvious, as all of the edges between the two graphs are in bijection with each other.

, and we color the edges as to specify a Hamiltonian decomposition (a decomposition into Hamiltonian paths, then those edges also form a Hamiltonian Decomposition in

The invariance of edge coloring and Hamiltonian Decomposition can be seen clearly.

is a bijection and is given as letters in the figure.

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

colors and satisfies certain properties (called an outline Hamiltonian decomposition).

In [3] 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.