1-factorización del gráfico de Desargues : cada clase de color es un 1-factor .El gráfico de Petersen se puede dividir en uno de 1 factor (rojo) y uno de 2 factores (azul). Sin embargo, el gráfico no es unifactorizable .
En teoría de grafos , un factor de un grafo G es un subgrafo generador , es decir, un subgrafo que tiene el mismo conjunto de vértices que G. Un k - factor de un grafo es un subgrafo generador regular k , y una k -factorización divide las aristas del grafo en k -factores disjuntos. Se dice que un grafo G es k -factorizable si admite una k -factorización. En particular, un 1-factor es una coincidencia perfecta , y una 1-factorización de un grafo k -regular es una coloración adecuada de las aristas con k colores. Un 2-factor es una colección de ciclos que abarca todos los vértices del grafo.
1-factorización
Si un grafo es 1-factorizable entonces tiene que ser un grafo regular . Sin embargo, no todos los grafos regulares son 1-factorizables. Un grafo k -regular es 1-factorizable si tiene índice cromático k ; algunos ejemplos de tales grafos incluyen:
Cualquier grafo bipartito regular . [1] El teorema del matrimonio de Hall se puede utilizar para demostrar que un grafo bipartito k -regular contiene una correspondencia perfecta. Se puede entonces eliminar la correspondencia perfecta para obtener un grafo bipartito ( k − 1)-regular y aplicar el mismo razonamiento repetidamente.
Cualquier gráfico completo con un número par de nodos (ver más abajo). [2]
Sin embargo, también hay gráficos k -regulares que tienen índice cromático k + 1, y estos gráficos no son 1-factorizables; ejemplos de dichos gráficos incluyen:
Cualquier gráfico regular con un número impar de nodos.
1-factorización de K 8 en la que cada 1-factor consiste en una arista desde el centro hasta un vértice de un heptágono junto con todas las aristas perpendiculares posibles
Un método para construir una factorización 1 de un grafo completo en un número par de vértices implica colocar todos los vértices menos uno en un polígono regular , con el vértice restante en el centro. Con esta disposición de vértices, una forma de construir un factor 1 del grafo es elegir una arista e desde el centro hasta un único vértice del polígono junto con todas las aristas posibles que se encuentran en líneas perpendiculares a e . Los factores 1 que se pueden construir de esta manera forman una factorización 1 del grafo.
El número de factorizaciones 1 distintas de K 2 , K 4 , K 6 , K 8 , ... es 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ( OEIS : A000438 ).
Conjetura de 1 factorización
Sea G un grafo k -regular con 2 n nodos. Si k es suficientemente grande, se sabe que G tiene que ser 1-factorizable:
Si k = 2 n − 1, entonces G es el gráfico completo K 2 n , y por lo tanto 1-factorizable (ver arriba).
Si k = 2 n − 2, entonces G se puede construir eliminando una correspondencia perfecta de K 2 n . Nuevamente, G es 1-factorizable.
Chetwynd y Hilton (1985) muestran que si k ≥ 12 n /7, entonces G es 1-factorizable.
La conjetura de factorización 1 [3] es una conjetura de larga data que establece que k ≈ n es suficiente. En términos precisos, la conjetura es:
Si n es impar y k ≥ n , entonces G es 1-factorizable. Si n es par y k ≥ n − 1 entonces G es 1-factorizable.
Un par perfecto de una factorización 1 es un par de factores 1 cuya unión induce un ciclo hamiltoniano .
Una factorización 1 perfecta (P1F) de un grafo es una factorización 1 que tiene la propiedad de que cada par de factores 1 es un par perfecto. Una factorización 1 perfecta no debe confundirse con una correspondencia perfecta (también llamada 1-factor).
En 1964, Anton Kotzig conjeturó que todo grafo completo K 2 n donde n ≥ 2 tiene una factorización 1 perfecta. Hasta ahora, se sabe que los siguientes grafos tienen una factorización 1 perfecta: [4]
la familia infinita de grafos completos K 2 p donde p es un primo impar (por Anderson y también Nakamura, independientemente),
la familia infinita de grafos completos K p +1 donde p es un primo impar,
y resultados adicionales esporádicos, incluyendo K 2 n donde 2 n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Algunos resultados más nuevos se recogen aquí.
Si el grafo completo K n +1 tiene una 1-factorización perfecta, entonces el grafo bipartito completo K n , n también tiene una 1-factorización perfecta. [5]
Si un grafo conexo es 2 k -regular y tiene un número par de aristas, también puede ser k -factorizado, eligiendo cada uno de los dos factores como un subconjunto alterno de las aristas de un recorrido de Euler . [7] Esto se aplica sólo a grafos conexos; los contraejemplos desconectados incluyen uniones disjuntas de ciclos impares, o de copias de K 2 k +1 .
El problema de Oberwolfach se refiere a la existencia de 2-factorizaciones de grafos completos en subgrafos isomorfos . Pregunta para qué subgrafos es posible esto. Esto se sabe cuando el subgrafo es conexo (en cuyo caso es un ciclo hamiltoniano y este caso especial es el problema de la descomposición hamiltoniana ), pero el caso general permanece abierto .
^ Chetwynd y Hilton (1985). Niessen (1994). Perkovic y Reed (1997). Oeste.
^ Wallis, WD (1997), "16. Factorizaciones perfectas", One-factorizations , Matemáticas y sus aplicaciones, vol. 390 (1.ª ed.), Springer US , pág. 125, doi :10.1007/978-1-4757-2564-3_16, ISBN978-0-7923-4323-3
^ Bryant, Darryn; Maenhaut, Barbara M.; Wanless, Ian M. (mayo de 2002), "Una familia de factorizaciones perfectas de gráficos bipartitos completos", Journal of Combinatorial Theory , A, 98 (2): 328–342, doi : 10.1006/jcta.2001.3240 , ISSN 0097-3165
^ Petersen (1891), §9, pág. 200. Harary (1969), Teorema 9.9, pág. 90. Véase Diestel (2005), Corolario 2.1.5, p. 39 para una prueba.
^ Petersen (1891), §6, pág. 198.
Bibliografía
Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones, Holanda Septentrional, ISBN 0-444-19451-7, archivado desde el original el 13 de abril de 2010 , consultado el 18 de diciembre de 2019, Sección 5.1: “Coincidencias”.
Chetwynd, AG ; Hilton, AJW (1985), "Los gráficos regulares de alto grado son 1-factorizables", Actas de la London Mathematical Society , 50 (2): 193–206, doi :10.1112/plms/s3-50.2.193.
Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 3-540-26182-6, Capítulo 2: “Emparejado, recubrimiento y empaquetado”. Edición electrónica.
Harary, Frank (1969), Teoría de grafos , Addison-Wesley, ISBN 0-201-02787-9, Capítulo 9: "Factorización".
Niessen, Thomas (1994), "Cómo encontrar subgrafos demasiado llenos en grafos con un grado máximo grande", Discrete Applied Mathematics , 51 (1–2): 117–125, doi :10.1016/0166-218X(94)90101-5.
Perkovic, L.; Reed, B. (1997), "Coloración de aristas de gráficos regulares de alto grado", Discrete Mathematics , 165–166: 567–578, doi :10.1016/S0012-365X(96)00202-6.
Plummer, Michael D. (2007), "Factores de gráficos y factorización: 1985-2003: una encuesta", Discrete Mathematics , 307 (7-8): 791-821, doi :10.1016/j.disc.2005.11.059.
