Arboricidad lineal

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

La arboricidad lineal de cualquier grafo de grado máximo${\displaystyle \Delta }$se sabe que es al menos${\displaystyle \lceil \Delta /2\rceil }$y se conjetura que es como máximo${\displaystyle \lceil (\Delta +1)/2\rceil }$Esta conjetura determinaría la arboricidad lineal con exactitud 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 un problema NP-completo .

Problema sin resolver en matemáticas

¿Cada gráfico de grado máximo?${\displaystyle \Delta }$tienen arboricidad lineal como máximo${\displaystyle \lceil (\Delta +1)/2\rceil }$¿

Más problemas sin resolver en matemáticas

La arboricidad lineal de un grafo${\displaystyle G}$con el máximo grado${\displaystyle \Delta }$siempre es al menos${\displaystyle \lceil \Delta /2\rceil }$, 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 ajustado: según su conjetura, cada grafo tiene arboricidad lineal como máximo${\displaystyle \lceil (\Delta +1)/2\rceil }$. ^{[ 1 ]} Sin embargo, esto sigue sin probarse , siendo el mejor límite superior probado para la arboricidad lineal algo mayor, ${\displaystyle \Delta /2+O(\Delta ^{2/3-c})}$por alguna constante${\displaystyle c>0}$debido a Ferber, Fox y Jain. ^{[ 2 ]}

Para que la arboricidad lineal de un gráfico sea igual${\displaystyle \Delta /2}$,${\displaystyle \Delta }$debe ser uniforme y cada bosque lineal debe tener dos aristas incidentes a cada vértice de grado${\displaystyle \Delta }$. 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${\displaystyle \Delta }$. Por lo tanto, un grafo cuya arboricidad lineal es igual a${\displaystyle \Delta /2}$debe tener algunos vértices cuyo grado sea menor que el máximo. En un grafo regular , no hay tales vértices, y la arboricidad lineal no puede ser igual.${\displaystyle \Delta /2}$Por lo tanto, para grafos regulares, la conjetura de arboricidad lineal implica que la arboricidad lineal es exactamente${\displaystyle \lceil (\Delta +1)/2\rceil }$.

La arboricidad lineal es una variación de la arboricidad , el número mínimo de bosques en los que se pueden particionar las aristas 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 aristas. ^{[ 3 ]}

Otro problema relacionado es la descomposición hamiltoniana , el problema de descomponer un grafo regular de grado par.${\displaystyle \Delta }$exactamente${\displaystyle \Delta /2}$Ciclos 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 /2}$.

A diferencia de la arboricidad, que puede determinarse en tiempo polinomial , la arboricidad lineal es NP-difícil . Incluso reconocer los grafos de arboricidad lineal dos es NP-completo . ^{[ 4 ]} Sin embargo, para grafos cúbicos y otros grafos de grado máximo tres, la arboricidad lineal siempre es 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 ]}