# Graph amalgamation

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_amalgamation
> Markdown URL: https://mediated.wiki/source/Graph_amalgamation.md
> Source: https://en.wikipedia.org/wiki/Graph_amalgamation
> Source revision: 1344401777
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [graph theory](/source/graph_theory), a '''graph amalgamation''' is a relationship between two graphs (one graph is an amalgamation of another).  Similar relationships include [subgraphs](/source/Glossary_of_graph_theory) and [minors](/source/graph_minor). 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,<ref name="gross">Gross, Tucker 1987</ref> computing  genus distribution,<ref name="jlg2">Gross 2011</ref> and [Hamiltonian decomposition](/source/Hamiltonian_decomposition)s.

== Definition ==

Let <math>G</math> and <math>H</math> be two graphs with the same number of edges where <math>G</math> has more vertices than <math>H</math>.  Then we say that <math>H</math> is an amalgamation of <math>G</math> if there is a [bijection](/source/bijection) <math>\phi: E(G) \to E(H)</math> and a [surjection](/source/surjection) <math>\psi: V(G) \to V(H)</math> and the following hold:
* If <math>x</math>, <math>y</math> are two vertices in <math>G</math> where <math>\psi(x) \neq \psi(y)</math>, and both <math>x</math> and <math>y</math> are adjacent by edge <math>e</math> in <math>G</math>, then <math>\psi(x)</math> and <math>\psi(y)</math> are adjacent by edge <math>\phi(e)</math> in <math>H</math>.
* If <math>e</math> is a loop on a vertex <math>x \in V(G)</math>, then <math> \phi(e)</math> is a loop on <math>\psi(x) \in H</math>.
* If <math>e</math> joins <math>x,y \in V(G)</math>, where <math>x \neq y</math>, but <math>\psi(x) = \psi(y)</math>, then <math>\phi(e)</math> is a loop on <math>\psi(x)</math>.<ref name="hilton">Hilton 1984</ref>

Note that while <math>G</math> can be a graph or a [pseudograph](/source/pseudograph), it will usually be the case that <math>H</math> is a pseudograph.

=== Properties ===
[Edge coloring](/source/Edge_coloring)s 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 <math>G</math> is a [complete graph](/source/complete_graph) of the form <math>K_{2n+1}</math>, and we color the edges as to specify a Hamiltonian decomposition (a decomposition into [Hamiltonian path](/source/Hamiltonian_path)s), then those edges also form a Hamiltonian Decomposition in <math>H</math>.

== Example ==
thumb|Figure 1: An amalgamation of the complete graph on five vertices.
Figure 1 illustrates an amalgamation of <math>K_5</math>.  The invariance of edge coloring and Hamiltonian Decomposition can be seen clearly. The function <math>\phi</math> is a bijection and is given as letters in the figure.  The function <math>\psi</math> is given in the table below.

{| class="wikitable"
|-
! <math>v \in V(G)</math> !! <math>\psi(v)</math>
|-
| <math>v_1</math> || <math>u_2</math>
|-
| <math>v_2</math> || <math>u_2</math>
|-
| <math>v_3</math> || <math>u_1</math>
|-
| <math>v_4</math> || <math>u_3</math>
|-
| <math>v_5</math> || <math>u_2</math>
|}

=== Hamiltonian decompositions ===
One of the ways in which amalgamations can be used is to find Hamiltonian Decompositions of complete graphs with 2''n''&nbsp;+&nbsp;1 vertices.<ref name="barg">Bahmanian, Amin; Rodger, Chris 2012</ref> The idea is to take a graph and produce an amalgamation of it which is edge colored in <math>n</math> colors and satisfies certain properties (called an outline Hamiltonian decomposition).  We can then 'reverse' the amalgamation  and we are left with <math>K_{2n+1}</math> colored in a Hamiltonian Decomposition.

In <ref name="hilton" /> 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.

== Notes ==
 {{Reflist}}

== References ==
* Bahmanian, Amin; Rodger, Chris (2012), [http://www.auburn.edu/academic/cosam/departments/math/images/Bahmanian2012.pdf "What Are Graph Amalgamations?"], [Auburn University](/source/Auburn_University)
* [Hilton, A. J. W](/source/Anthony_Hilton) (1984), [https://www.sciencedirect.com/science/article/pii/0095895684900200 "Hamiltonian Decompositions of Complete Graphs], [Journal of Combinatorial Theory](/source/Journal_of_Combinatorial_Theory), Series B 36, 125–134
* Gross, Jonathan L.; Tucker, Thomas W.  (1987),   Topological Graph Theory, [Courier Dover Publications](/source/Dover_Publications), 151
* Gross, Jonathan L. (2011), [http://www.emis.de/journals/JGAA/getPaper-86.html?id=227  "Genus Distributions of Cubic Outerplanar Graphs"],  [Journal of Graph Algorithms and Applications](/source/Journal_of_Graph_Algorithms_and_Applications), Vol. 15, no. 2, pp.&nbsp;295–316

Category:Graph theory

---
Adapted from the Wikipedia article [Graph amalgamation](https://en.wikipedia.org/wiki/Graph_amalgamation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_amalgamation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.