Arboricidad lineal

Partición del grafo de un dodecaedro rómbico en dos bosques lineales , mostrando que su arboricidad lineal es dos

En teoría de grafos , una rama de las matemáticas , la arboricidad lineal de un grafo no dirigido es el número más pequeño de bosques lineales en los que se pueden dividir sus aristas. Aquí, un bosque lineal es un grafo acíclico con un grado máximo de dos; es decir, es una unión disjunta de grafos de trayectorias . La arboricidad lineal es una variante de la arboricidad , el número mínimo de bosques en los que se pueden dividir las aristas.

Se sabe que la arboricidad lineal de cualquier grafo de grado máximo es al menos y se conjetura que es como máximo . Esta conjetura determinaría la arboricidad lineal exactamente para grafos de grado impar , ya que en ese caso ambas expresiones son iguales. Para grafos de grado par implicaría que la arboricidad lineal debe ser uno de solo dos valores posibles, pero determinar el valor exacto entre estas dos opciones es NP-completo . ${\displaystyle \Delta }$ ${\displaystyle \lceil \Delta /2\rceil }$ ${\displaystyle \lceil (\Delta +1)/2\rceil }$

Relación con el grado

Problema sin resolver en matemáticas :

¿Todo grafo de grado máximo tiene arboricidad lineal como máximo ? ${\displaystyle \Delta }$ ${\displaystyle \lceil (\Delta +1)/2\rceil }$

(más problemas sin resolver en matemáticas)

La arboricidad lineal de un grafo con grado máximo es siempre al menos , porque cada bosque lineal puede usar solo dos de las aristas en un vértice de grado máximo. La conjetura de arboricidad lineal de Akiyama, Exoo y Harary (1981) es que este límite inferior también es estricto: según su conjetura, cada grafo tiene arboricidad lineal como máximo . ^[1] Sin embargo, esto sigue sin demostrarse , y el mejor límite superior demostrado de la arboricidad lineal es algo mayor, para alguna constante debido a Ferber, Fox y Jain. ^[2] ${\displaystyle G}$ ${\displaystyle \Delta }$ ${\displaystyle \lceil \Delta /2\rceil }$ ${\displaystyle \lceil (\Delta +1)/2\rceil }$ ${\displaystyle \Delta /2+O(\Delta ^{2/3-c})}$ ${\displaystyle c>0}$

Para que la arboricidad lineal de un grafo sea igual a , debe ser par y cada bosque lineal debe tener dos aristas incidentes a cada vértice de grado . Pero en un vértice que está al final de un camino, el bosque que contiene ese camino tiene solo una arista incidente, por lo que el grado en ese vértice no puede ser igual a . Por lo tanto, un grafo cuya arboricidad lineal sea igual a debe tener algunos vértices cuyo grado sea menor que el máximo. En un grafo regular , no existen tales vértices, y la arboricidad lineal no puede ser igual a . Por lo tanto, para grafos regulares, la conjetura de arboricidad lineal implica que la arboricidad lineal es exactamente . ${\displaystyle \Delta /2}$ ${\displaystyle \Delta }$ ${\displaystyle \Delta }$ ${\displaystyle \Delta }$ ${\displaystyle \Delta /2}$ ${\displaystyle \Delta /2}$ ${\displaystyle \lceil (\Delta +1)/2\rceil }$

Problemas relacionados

La arboricidad lineal es una variación de la arboricidad , el número mínimo de bosques en los que se pueden dividir los bordes de un grafo. Los investigadores también han estudiado la k -arboricidad lineal, una variante de la arboricidad lineal en la que cada camino en el bosque lineal puede tener como máximo k bordes. ^[3]

Otro problema relacionado es la descomposición hamiltoniana , el problema de descomponer un grafo regular de grado par en ciclos exactamente hamiltonianos . Un grafo dado tiene una descomposición hamiltoniana si y solo si el subgrafo formado al eliminar un vértice arbitrario del grafo tiene arboricidad lineal . ${\displaystyle \Delta }$ ${\displaystyle \Delta /2}$ ${\displaystyle \Delta /2}$

Complejidad computacional

A diferencia de la arboricidad, que se puede determinar en tiempo polinomial , la arboricidad lineal es NP-hard . Incluso reconocer los grafos de arboricidad lineal dos es NP-completo . ^[4] Sin embargo, para grafos cúbicos y otros grafos de máximo grado tres, la arboricidad lineal es siempre dos, ^[1] y se puede encontrar una descomposición en dos bosques lineales en tiempo lineal utilizando un algoritmo basado en búsqueda en profundidad . ^[5]

Referencias

1. Akiyama, Jin ; Exoo, Geoffrey; Harary, Frank (1981), "Cobertura y empaquetamiento en grafos. IV. Arboricidad lineal", Networks , 11 (1): 69–72, doi :10.1002/net.3230110108, MR  0608921.
2. Ferber, Asaf; Fox, Jacob ; Jain, Vishesh (2018), Hacia la conjetura de arboricidad lineal , arXiv : 1809.04716.
3. Alon, Noga ; Teague, VJ ; Wormald, NC (2001), "Arboricidad lineal y k -arboricidad lineal de grafos regulares", Graphs and Combinatorics , 17 (1): 11–16, doi :10.1007/PL00007233, MR  1828624.
4. Péroche, B. (1984), "NP-completitud de algunos problemas de partición y cubrimiento en grafos", Discrete Applied Mathematics , 8 (2): 195–208, doi : 10.1016/0166-218X(84)90101-X , MR  0743024; véase también Péroche, B. (1982), "Complexité de l'arboricité linéaire d'un graphe", RAIRO Recherche Opérationnelle , 16 (2): 125–129, doi : 10.1051/ro/1982160201251 , MR  0679633y Péroche, B. (1985), "Complexité de l'arboricité linéaire d'un graphe. II", RAIRO Recherche Opérationnelle , 19 (3): 293–300, doi : 10.1051/ro/1985190302931 , MR  0815871. Una reducción de Péroche (1982) de multigrafos a grafos simples se repite en Shermer, Thomas C. (1996), "On rectangle transparency graphs. III. External transparency and complex" (PDF) , Actas de la 8.ª Conferencia Canadiense sobre Geometría Computacional (CCCG'96) , págs. 234-239..
5. Duncan, Christian A.; Eppstein, David ; Kobourov, Stephen G. (2004), "El espesor geométrico de los grafos de bajo grado", Proc. 20.º Simposio ACM sobre geometría computacional (SoCG 2004) , págs. 340–346, arXiv : cs.CG/0312056 , doi :10.1145/997817.997868, ISBN 1-58113-885-7.