¿Cuál es el efecto de añadir una arista en el número de árboles de expansión de un gráfico dado?

Question

Hola,

Definir $C(G)$ el número de árboles de distribución en un gráfico $G$ .

Ahora, dado un gráfico $G$ con $n$ vértices y $p$ aristas, construye un nuevo gráfico $G'$ que es igual al gráfico $G$ pero en el que se añade exactamente una nueva arista.

La pregunta es: ¿podemos saber algo sobre la fracción $\frac{C(G)}{C(G')}$ ?

Tal vez podamos utilizar que el número de árboles de extensión de un grafo es igual al determinante de cualquier cofactor de la matriz laplaciana del grafo. (Porque las dos matrices laplacianas están aquí muy cerca) ? Lo he intentado así pero sin éxito todavía.

Answer 1

Si la nueva arista conecta vértices $v$ y $w$ entonces $C(G')/C(G) - 1$ es el resistencia eléctrica entre $v$ y $w$ en $G$ donde todas las aristas tienen una resistencia de $1$ . (Las versiones ponderadas también funcionan.) Un límite superior para esta resistencia (que proporciona un límite inferior en $C(G)/C(G')$ ) es la distancia entre $v$ y $w$ y la máxima resistencia finita se produce cuando $G$ es una ruta de $n$ vértices de $v$ à $w$ para que $C(G')$ es $n$ (árboles de extensión de un ciclo) mientras que $C(G) = 1$ .

Supongo que la resistencia mínima con $p=n+k$ bordes se produce cuando el borde entre $v$ y $w$ es lo más redundante posible, con $k+2$ bordes entre ellos, con cualquier bosque colgando de este borde repetido. Eso da una resistencia de $1/(k+2)$ y luego $C(G) = k+2$ mientras que $G(G') = k+3$ . Creo que la resistencia mínima es sólo un poco más complicada si se requiere que los gráficos sean simples: Maximizar los caminos de longitud $2$ .

Answer 2

A veces, cuando se trata de gráficos concretos, este límite puede ser útil.

Dejemos que $f(G) = max_{u \not \sim v} C(G/uv)$ donde $G/uv$ se obtiene tras contraer dos vértices no adyacentes $u,v$ de $G$ en un solo vértice.

A partir de la recurrencia de la contracción de la supresión sabemos que $$C(G') = C(G+e) = C(G)+C( (G+e)/e) \leq C(G)+f(G)$$ desde donde se puede obtener fácilmente un límite para $\frac{C(G)}{C(G')}$

De la misma manera se puede obtener un límite inferior para $\frac{C(G)}{C(G')}.$