Encontrar gráficos con un número determinado de árboles de expansión

Question

Todos los gráficos en cuenta en esta pregunta están conectados. Podemos encontrar el número de árboles de expansión $t(G)$ $G$ el uso de Kirchhoff de la matriz de árbol teorema o la eliminación-la contracción del método. Estoy interesado en el recíproco de este problema. Es decir, dada $n$, encontramos a $G$ tal que $t(G)=n$.

Sin algunas restricciones en $G$ este problema se convierte en algo casi trivial. Por ejemplo, el ciclo de $C_n$ $n$ árboles de expansión. Además, si se identifica un vértice de gráficos de $G$$H$, el gráfico resultante ha $t(G) \cdot t(H)$ árboles de expansión. Del mismo modo, si nos unimos $G$ $H$ con cualquier ruta de acceso. Así que si podemos factor de $n$ que acaba de estar tratando con la misma pregunta para los números más pequeños. Por ello me gustaría restringir $G$ de un ciclo o un gráfico con un corte de vértice o del corte-borde.

Mi pregunta entonces es, dado $n$, podemos siempre encontrar un gráfico de $G$ que no es un ciclo y que no tiene corte de vértices o de corte de bordes, que $t(G)=n$? Si es posible encontrar uno, es posible encontrar muchos, o todos los gráficos que cumplen esas propiedades? Si no es posible, en general, somos capaces de determinar que $n$ es cierto?

He pasado por todas las gráficas de hasta seis vértices de http://www.graphclasses.org/smallgraphs.html y calcula el número de árboles de expansión para cada uno. El más pequeño gráfico que cumple con todos los criterios es $K_4-e$, el cual tiene 8 árboles de expansión. Los primeros diez $n>8$ por que no he encontrado una respectivas $G$ 9, 10, 13, 18, 22, 25, 33, 37, 42, y 46. Todos estos números son uno menos que en un primer o uno menos de 2 veces a la prime.

Gracias.

Answer 1

Deje $n = pq$ para dos números de $p,q \geq 3.$ Considere la gráfica de $B_{p,q}$ obtenido por la toma de los dos ciclos de longitud $p$ $q$ que comparten un vértice común. A continuación,$t(B_{p,q}) = pq = n.$, por tanto, para cualquier $n$ que tiene dos divisores $\geq 2$ usted puede encontrar un gráfico de la satisfacción de su igualdad. Tenga en cuenta que usted puede generalizar a cualquier número de divisores de a $n$ mientras que todos ellos son mayores de $2.$

La segunda cosa es considerar la theta grafo $\Theta_{a,b,c}$ que es la gráfica obtenida por la toma de tres internamente disjuntos caminos de longitud $a,b$ $c$ respectivamente.

Es fácil ver que $t(\Theta_{a,b,c}) = ab+ac+bc$ y por lo tanto, si usted puede expresar $n = ab+ac+bc$ $a \geq 1$ $b,c \geq 2$ se puede obtener el gráfico deseado.

Es bien sabido que hay sólo un número finito de números de $n$ que no se pueden expresar como $n = ab+ac+bc.$ son llamados Euler Idoneal números.

Por lo tanto, para cualquiera, pero un número finito de $n$ usted puede encontrar una $2$-gráfica conectada la satisfacción de su igualdad.

Más específicamente otorgada $n \geq 2$ usted puede encontrar una $2$-gráfica conectada $G$ que no es un ciclo tal que $t(G) = n$ si y sólo si $n \not \in \{3,4,5,6,7,9,10,13,18,22,X \}.$ Donde $X$ es un Idoneal número de cuya existencia no es conocida. Vea también de este artículo si usted está interesado en este problema.