Núcleo (teoría de grafos)

En el campo matemático de la teoría de grafos , un núcleo es una noción que describe el comportamiento de un grafo con respecto a los homomorfismos de grafos .

Definición

Graph es un núcleo si cada homomorfismo es un isomorfismo , es decir, es una biyección de vértices de . ${\displaystyle C}$ ${\displaystyle f:C\to C}$ ${\displaystyle C}$

Un núcleo de un gráfico es un gráfico tal que ${\displaystyle G}$ ${\displaystyle C}$

1. Existe un homomorfismo de a , ${\displaystyle G}$ ${\displaystyle C}$
2. existe un homomorfismo de a , y ${\displaystyle C}$ ${\displaystyle G}$
3. ${\displaystyle C}$es mínimo con esta propiedad.

Se dice que dos gráficos son equivalentes de homomorfismo o equivalentes de hom si tienen núcleos isomórficos.

Ejemplos

• Cualquier gráfico completo es un núcleo.
• Un ciclo de duración impar es un núcleo.
• Un gráfico es un núcleo si y sólo si el núcleo de es igual a . ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$
• Cada dos ciclos de longitud par y, de manera más general, cada dos gráficos bipartitos son homequivalentes. El núcleo de cada uno de estos gráficos es el gráfico completo de dos vértices K ₂ .
• Según el teorema de Beckman-Quarles , el gráfico de distancia unitaria infinita en todos los puntos del plano euclidiano o de cualquier espacio euclidiano de dimensiones superiores es un núcleo.

Propiedades

Todo grafo finito tiene un núcleo, que está determinado de forma única, hasta el isomorfismo . El núcleo de un gráfico G es siempre un subgrafo inducido de G. Si y entonces las gráficas y son necesariamente homomórficamente equivalentes . ${\displaystyle G\to H}$ ${\displaystyle H\to G}$ ${\displaystyle G}$ ${\displaystyle H}$

Complejidad computacional

Es NP-completo para probar si un gráfico tiene un homomorfismo con respecto a un subgrafo adecuado, y co-NP-completo para probar si un gráfico es su propio núcleo (es decir, si no existe tal homomorfismo) (Hell y Nešetřil 1992).

Referencias

• Godsil, Chris y Royle, Gordon . Teoría de grafos algebraica. Textos de Posgrado en Matemáticas, vol. 207. Springer-Verlag, Nueva York, 2001. Capítulo 6 sección 2.
• Demonios, Pavol ; Nešetřil, Jaroslav (1992), "El núcleo de un gráfico", Matemáticas discretas , 109 (1–3): 117–126, doi : 10.1016/0012-365X(92)90282-K , MR  1192374.
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "Proposición 3.5", Escasez: gráficos, estructuras y algoritmos , Algoritmos y combinatoria, vol. 28, Heidelberg: Springer, pág. 43, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, señor  2920058.