Factorización de gráficos

Un factor de un gráfico G es un subgráfico generador, es decir, un subgráfico que tiene los mismos vértices que el gráfico G. El factor k del gráfico es un subgráfico regular k que se expande , y la factorización k divide los bordes del gráfico en factores k que no se intersecan . Se dice que un grafo G es k -factorizable si permite una k -partición. En particular, el conjunto de aristas de un factor 1 es una combinación perfecta , y la descomposición en 1 de un gráfico regular k es una coloración de aristas con k colores. Un factor 2 es un conjunto de ciclos que cubren todos los vértices del gráfico.

Factorización en 1

Si un gráfico es factorizable en 1 (es decir, tiene una factorización en 1), entonces debe ser un gráfico regular . Sin embargo, no todos los gráficos regulares son factorizables en 1. Un gráfico k -regular es factorizable en 1 si su índice cromático es k . Ejemplos de tales gráficos:

Cualquier gráfico bipartito regular [1] [2] . El teorema de la boda de Hall se puede usar para mostrar que un gráfico bipartito k -regular contiene una coincidencia perfecta. Luego, se puede eliminar la coincidencia perfecta y el gráfico bipartito regular ( k − 1) y continuar el mismo proceso recursivamente.
Cualquier gráfico completo con un número par de vértices (ver más abajo ) [3] .

Sin embargo, hay gráficos k -regulares cuyo índice cromático es k + 1, y estos gráficos no son factorizables en 1. Ejemplos de tales gráficos:

Cualquier gráfico regular con un número impar de vértices.
Conde Petersen .

Gráficos completos

La factorización 1 de un gráfico completo corresponde al emparejamiento en torneos de todos contra todos . La factorización en 1 de gráficos completos es un caso especial del teorema de Baranyai con respecto a la factorización en 1 de hipergrafías completas .

Una forma de construir una factorización en 1 de un gráfico completo coloca todos menos uno de los vértices en el círculo, formando un polígono regular , mientras que el vértice restante se coloca en el centro del círculo. Con esta disposición de vértices, el proceso de construcción de un factor 1 consiste en elegir una arista e que conecte el vértice central con uno de los vértices del círculo, luego se seleccionan todas las aristas perpendiculares a la arista e . Los factores de 1 construidos de esta manera forman una factorización de 1 del gráfico.

El número de factorizaciones distintas de 1 es 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, … (secuencia A000438 en OEIS ). $K_{2},K_{4},K_{6},K_{8},\puntos$

La conjetura de factorización en 1

Sea G un grafo k -regular con 2n vértices. Si k es lo suficientemente grande, se sabe que G debe ser factorizable en 1:

Si , entonces G es un gráfico completo y, por lo tanto, factorizable en 1 (ver arriba ). ${\ estilo de visualización k = 2n-1}$ ${\ Displaystyle K_ {2n}}$
Si , entonces G puede obtenerse eliminando una combinación perfecta de . De nuevo , G es factorizable en 1. ${\ estilo de visualización k = 2n-2}$ ${\ Displaystyle K_ {2n}}$
Chetwynd y Hilton [4] demostraron que para , el gráfico G es factorizable en 1. $k\geqslant {\tfrac {12n}{7))$

La conjetura de factorización en 1 [5] es una conjetura de larga data que afirma que el valor es suficientemente grande. Redacción exacta: ${\ estilo de visualización k \ aproximadamente n}$

Si n es impar y , entonces G es factorizable en 1. Si n es par y , entonces G es factorizable en 1. ${\ Displaystyle k\ geqslant n}$ $k\geqslant n-1$

La conjetura de relleno pesado incluye la conjetura de factorización en 1.

Perfecta factorización en 1

Un par perfecto de factorizaciones de 1 es un par de factores de 1 cuya unión da un ciclo hamiltoniano .

Una factorización perfecta en 1 (P1F) de un gráfico es una factorización en 1 que tiene la propiedad de que cualquier par de factores 1 es un par perfecto. Una factorización perfecta de 1 no debe confundirse con una combinación perfecta (también llamada factor de 1).

En 1964, Anton Kotzig conjeturó que cualquier gráfico completo , donde , tiene una factorización perfecta en 1. Se sabe que las siguientes gráficas tienen factorizaciones perfectas en 1 [6] : ${\ Displaystyle K_ {2n}}$ $n \geqslant 2$

Una familia infinita de grafos completos , donde p es un primo impar (Anderson y Nakamura, independientemente), ${\ Displaystyle K_ {2p}}$
Una familia infinita de grafos completos , donde p es un primo impar $K_{p+1}$
esporádicamente otras gráficas, incluyendo , donde . También hay resultados más recientes aquí . ${\ Displaystyle K_ {2n}}$ ${\displaystyle 2n\in \{16,28,36,40,50,126,170,244,344,730,1332,1370,1850,2198,3126,6860,12168,16808,29792\))$

Si un gráfico completo tiene una factorización perfecta en 1, entonces un gráfico bipartito completo también tiene una factorización perfecta en 1 [7] . $K_{n+1}$ $K_{{n,n}}$

2-factorización

Si un gráfico es factorizable en 2, entonces debe ser 2 k -regular para algún entero k . Julius Petersen demostró en 1891 que esta condición necesaria también es suficiente: cualquier gráfico regular de 2k es factorizable en 2 [8] .

Si un gráfico conexo es 2k -regular y tiene un número par de aristas, también puede ser k -factorizable eligiendo dos factores que sean aristas alternas del ciclo de Euler [9] . Esto se aplica solo a gráficos conectados, los contraejemplos desconectados contienen una unión desconectada de ciclos impares o copias del gráfico K 2 k +1 .

Notas

↑ Harari, 2003 , pág. 107, Teorema 9.2.
↑ Distel, 2002 , pág. 48, Corolario 2.1.3.
↑ Harari, 2003 , pág. 85, Teorema 9.1.
↑ Chetwynd, Hilton, 1985 .
↑ Chetwynd, Hilton, 1985 ; Niessen, 1994 ; Perkovic, Reed, 1997 ; Oeste, 1985
↑ Wallis, 1997 , pág. 125.
↑ Bryant, Maenhaut, Wanless, 2002 , pág. 328–342.
↑ Petersen, 1891 , § 9, página 200; Harari, 2003 , página 113, Teorema 9.9; Véase la prueba en Distel, 2002 , página 49, Corolario 2.1.5
↑ Petersen, 1891 , pág. 198 §6.

Literatura

John Adrian Bondy, USR Murty. Apartado 5.1: "Emparejamientos". // Teoría de grafos con aplicaciones . - Holanda Septentrional, 1976. - ISBN 0-444-19451-7 . Archivado el 16 de junio de 2012 en Wayback Machine .
AG Chetwynd, AJW Hilton. Los gráficos regulares de alto grado son factorizables en 1 // Actas de la London Mathematical Society. - 1985. - T. 50 , núm. 2 . - S. 193-206 . -doi : 10.1112 / plms/s3-50.2.193 . .
Reinhard Distel. Capítulo 2: Emparejamiento // Teoría de grafos. - Novosibirsk: Editorial del Instituto de Matemáticas, 2002. - ISBN 5-86134-101-X , UDC 519.17, LBC 22.17.
F. Harari. Capítulo 9 Factorización // Teoría de grafos. - M .: Editorial URSS, 2003. - ISBN 5-354-00301-6 .

Tomás Niessen. Cómo encontrar subgráficos demasiado llenos en gráficos con un grado máximo grande // Matemáticas aplicadas discretas. - 1994. - T. 51 , núm. 1-2 . - S. 117-125 . - doi : 10.1016/0166-218X(94)90101-5 . .
L. Perkovic, B. Reed. Edge coloreando grafos regulares de alto grado // Matemáticas Discretas . - 1997. - T. 165-166 . - S. 567-578 . - doi : 10.1016/S0012-365X(96)00202-6 . .
Julio Peterson. Die Theorie der regulären grafos // Acta Mathematica . - 1891. - T. 15 . - S. 193-220 . -doi : 10.1007/ BF02392606 .
Douglas B. Oeste. 1-Conjetura de factorización (¿1985?) . Problemas abiertos - Teoría de grafos y combinatoria . Recuperado: 9 de enero de 2010. (indefinido)
W. D. Wallis. factorizaciones uni. - Springer EE . UU ., 1997. - T. 390 , no. 1 . - art. 125 . - ISBN 978-0-7923-4323-3 . -doi : 10.1007 / 978-1-4757-2564-3_16 .
Factorización en una / Michiel Hazewinkel. - Springer, 2001. - ISBN 978-1-55608-010-4 . (enlace no disponible)
Darryn Bryant, Barbara M. Maenhaut, Ian M. Wanless. Una familia de factorizaciones perfectas de gráficos bipartitos completos // Revista de teoría combinatoria. - 2002. - T. 98 , núm. 2 . - S. 328-342 . — ISSN 0097-3165 . -doi : 10.1006/ jcta.2001.3240 .

Weisstein, Eric W. Graph Factor en Wolfram MathWorld .
Weisstein, Eric W. k-Factor (inglés) en el sitio web Wolfram MathWorld .
Weisstein, Eric W. k - Gráfico factorizable en Wolfram MathWorld .

Lectura para leer más

Michael D. Plummer. Gráfico de factores y factorización: 1985–2003: una encuesta // Matemáticas discretas . - 2007. - T. 307 , núm. 7-8 . - S. 791-821 . -doi : 10.1016/ j.disco.2005.11.059 .