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

Un grafo es un núcleo si todo 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 grafos son homomorfistas equivalentes u hom-equivalentes si tienen núcleos isomorfos.

Ejemplos

• Cualquier gráfico completo es un núcleo.
• Un ciclo de longitud 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, más generalmente, cada dos grafos bipartitos son hom-equivalentes. El núcleo de cada uno de estos grafos es el grafo completo de dos vértices K ₂ .
• Según el teorema de Beckman-Quarles , el grafo de distancia unitaria infinita en todos los puntos del plano euclidiano o de cualquier espacio euclidiano de dimensión superior es un núcleo.

Propiedades

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

Complejidad computacional

Es NP-completo probar si un gráfico tiene un homomorfismo con un subgráfico apropiado, y co-NP-completo 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 algebraicos. 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 Mendez, Patrice (2012), "Proposición 3.5", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 43, doi :10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, Sr.  2920058.