Grado mínimo de la "gráfica de árbol"

Dado un gráfico $G$ , define el gráfico de árbol $T(G)$ como un gráfico cuyos vértices son los árboles de expansión de $G$ , y hay un borde entre dos árboles si se puede obtener uno del otro reemplazando un solo borde. Es que hay un borde $(T_1, T_2)$ si existe dos aristas $x, y \in G$ tal que $T_1 - x = T_2 - y$ .

Mi pregunta es esta: ¿hay algunos límites inferiores o superiores no triviales en el grado del vértice con un grado mínimo en $T(G)$ ?

Nota: edité un poco la pregunta (última línea) para que sea menos ambigua.

graph-theory tree corwin
fuente

Su definición de una ventaja no tiene sentido. ¿Quieres decir "hay un límite entre

T_{1}

$T_1$ y

T_{2}

$T_2$ si existe dos aristas

x, y \in G

$x, y \in G$ tal que

T_{1} - x + y = T_{2}

$T_1 - x + y = T_2$ "?

Tyson Williams

Sí, lo siento, quise decir bordes.

corwin

G

$G$ es un árbol, su gráfica de árbol

T (G)

$T(G)$ es un vértice único con grado 0. Por otro lado, si

G

$G$ es un gráfico completo, cada vértice en

T (G)

$T(G)$ tiene grado

Θ (n^{2})

$\Theta(n^2)$ . ¿Qué quiere decir exactamente con "no trivial"?

Jeffε

También es claramente mayor que la conectividad de

G

$G$ menos 1. ¿Es esto trivial? Debe ampliar su pregunta con lo que ya sabe sobre el problema, para que podamos juzgar lo que considera trivial y lo que no.

Artem Kaznatcheev

@Jeffe no creo

Θ (n^{2})

$\Theta(n^2)$ para un gráfico completo es correcto. Tomemos, por ejemplo, un árbol que es una línea. Eliminar un borde del árbol desconectará el árbol en dos grupos.

S

$S$ y

T

$T$ . Ahora hay

| S | \cdot | T |

$|S|\cdot|T|$ bordes que se pueden agregar para convertirlo en un árbol nuevamente. Asumiendo todos los bordes de ese árbol, vemos que hay

Θ (n^{3})

$\Theta(n^3)$ Árboles cercanos.

corwin

Respuestas:

Si $G$ tiene $n$ vértices y $m$ bordes, luego para cualquier árbol de expansión $T$ de $G$ , cada una de las $m-n+1$ bordes que no están en $T$ puede intercambiarse con cualquiera de los bordes del camino en $T$ entre los puntos finales del borde no arbóreo. Asumiendo $G$ no es un multigrafo, esto da al menos $2(m-n+1)$ diferentes intercambios; es decir, cada $T$ tiene grado al menos $2(m-n+1)$ .

Este límite es apretado: si $G$ tiene un vértice $v$ adyacente a todos los demás, y $T$ es el árbol de expansión que consta de todos los bordes incidentes a $v$ , entonces el camino en $T$ entre los puntos finales $T$ de cada borde que no es de árbol tiene una longitud exactamente dos, por lo que cada borde que no es de árbol participa exactamente en dos intercambios y $T$ tiene grado exactamente $2(m-n+1)$ .

Por otro lado si $G$ tiene circunferencia (duración del ciclo más corta) $g$ , entonces la ruta en cualquier árbol $T$ entre los puntos finales de cualquier borde que no sea de árbol, junto con ese borde, forma un ciclo que debe tener una longitud de al menos $g$ , por lo que el grado mínimo en el gráfico de árbol debe ser al menos $(g-1)(m-n+1)$ . Este límite es ajustado para algunos gráficos, como los gráficos de ciclo, y los gráficos bipartitos completos, y los gráficos de Moore, ya que estos gráficos contienen árboles de expansión para los cuales todos los bordes que no son árboles inducen ciclos de longitud igual a la circunferencia.

Sin embargo, encontrar el grado mínimo del gráfico de árbol para un gráfico dado arbitrariamente (equivalentemente, encontrar un árbol de expansión que minimice la suma de las longitudes de los ciclos inducidos por los bordes que no son de árbol) es NP completo: ver Deo, Prabhu y Krishnamoorthy, "Algoritmos para generar ciclos fundamentales en un gráfico", ACM TOMS 1982 . Por lo tanto, encontrar límites como estos que sean ajustados para todos los gráficos parece poco probable.

David Eppstein
fuente

Gracias por la excelente respuesta. ¿Podemos encontrar un límite superior ajustado que sea correcto para todos los gráficos?

Corwin

Además, ¿hay un límite superior conocido en la circunferencia de un gráfico conectado con

n

$n$ vértices y

m

$m$ bordes?

Corwin