fusión de gráficos

En teoría de grafos , una amalgama de grafos es una relación entre dos grafos (un grafo es una amalgama de otro). Relaciones similares incluyen subgrafos y menores . Las amalgamas pueden proporcionar una forma de reducir un grafo a uno más simple manteniendo cierta estructura intacta. La amalgama puede entonces usarse para estudiar propiedades del grafo original en un contexto más fácil de entender. Las aplicaciones incluyen incrustaciones, ^{[ 1 ]} el cálculo de la distribución de género, ^{[ 2 ]} y descomposiciones hamiltonianas .

Dejar${\displaystyle G}$y${\displaystyle H}$sean dos grafos con el mismo número de aristas donde${\displaystyle G}$tiene más vértices que${\displaystyle H}$Entonces decimos que${\displaystyle H}$es una amalgama de${\displaystyle G}$si existe una biyección${\displaystyle \phi:E(G)\a E(H)}$y una sobreyección${\displaystyle \psi:V(G)\a V(H)}$y lo siguiente se mantiene:

• Si${\displaystyle x}$,${\displaystyle y}$son dos vértices en${\displaystyle G}$dónde${\displaystyle \psi (x)\neq \psi (y)}$y ambos${\displaystyle x}$y${\displaystyle y}$son adyacentes por borde${\displaystyle e}$en${\displaystyle G}$, entonces${\displaystyle \psi (x)}$y${\displaystyle \psi (y)}$son adyacentes por borde${\displaystyle \phi (e)}$en${\displaystyle H}$.
• Si${\displaystyle e}$es un bucle en un vértice${\displaystyle x\in V(G)}$, entonces${\displaystyle \phi (e)}$es un bucle en${\displaystyle \psi (x)\in H}$.
• Si${\displaystyle e}$se une${\displaystyle x,y\in V(G)}$, dónde${\displaystyle x\neq y}$, pero${\displaystyle \psi (x)=\psi (y)}$, entonces${\displaystyle \phi (e)}$es un bucle en${\displaystyle \psi (x)}$. ^{[ 3 ]}

Tenga en cuenta que mientras${\displaystyle G}$puede ser un grafo o un pseudografo , por lo general será el caso que${\displaystyle H}$es un pseudografo.

La figura 1 ilustra una amalgama de${\displaystyle K_{5}}$. La invariancia del coloreado de bordes y la descomposición hamiltoniana se puede ver claramente. La función${\displaystyle \phi }$es una biyección y se representa con letras en la figura. La función${\displaystyle \psi }$se muestra en la tabla a continuación.

• Bahmanian, Amin; Rodger, Chris (2012), "¿Qué son las amalgamas de grafos?" , Universidad de Auburn
• Hilton, AJ W (1984), "Descomposiciones hamiltonianas de grafos completos" , Journal of Combinatorial Theory , Serie B 36, 125–134
• Gross, Jonathan L.; Tucker, Thomas W. (1987), Teoría topológica de grafos, Courier Dover Publications , 151
• Gross, Jonathan L. (2011), "Distribuciones de género de grafos cúbicos exteriores planares" , Journal of Graph Algorithms and Applications , vol. 15, n.º 2, págs.  295–316