Cuántos subdiagramas de $G$ hay en $K_n$?

Question

Deje $G$ un gráfico en $n$ vértices y $m$ bordes. Cuántas copias de $G$ hay en el grafo completo $K_n$?

Por ejemplo, si tenemos $C_4$, $3$ subdiagramas de $C_4$$K_4$, como se ve a continuación.

Sin embargo, si tenemos un gráfico diferente $G$ con la misma cantidad de aristas y vértices $C_4$, se puede obtener un número diferente de subdiagramas, como se ve a continuación.

Hay una fórmula general para este? Me siento como que he leído acerca de esto antes (tal vez en Wolfram), pero el problema del nombre se me escapa.

Answer 1

Este es un simple ejemplo de órbita-estabilizador: cada permutación de las $n$ vértices induce una incrustación de $G$$K_n$, pero dos permutaciones resultado en el mismo subgrafo iff se diferencian por un automorphism de $G$. Por lo tanto el número de los distintos subdiagramas es sólo $n!/|\text{Aut}(G)|$.

Para el segundo caso, $|\text{Aut}(G)| = 2$ debido a que usted puede intercambiar los dos vértices de grado $2$. Para el $4$-en el caso del ciclo, $\text{Aut}(C_4)$ es el diedro grupo en $4$ puntos, que tiene orden de $8$. Esto predice correctamente la observó $12$ $3$ subdiagramas, respectivamente.

Answer 2

Puedo estar equivocado, pero a menos $G$ tiene una estructura muy simple, yo no esperaría que haya una conocida fórmula para el número de los distintos subdiagramas de $K_n$ que son isomorfos a $G$.

Mi sensación es que el mejor que se puede aspirar es a ser capaz de responder a la pregunta para casos especiales, e incluso entonces, en tales casos, normalmente se necesita razonamiento personalizado para el caso especial.

Si el problema es de su interés, en lugar de pedir respuestas, continuar a explorar, sin siquiera tomarse la molestia de hacer una búsqueda en internet.

Por ejemplo, para empezar, tratar el problema para el caso en que:

• $G$ es un camino de longitud $k$.
• $G$ es un ciclo de longitud $k$.
• $G$ $k$ vértices, todos de grado $0$.
• $G$ $k$ vértices, todos de grado $1$.
• $G$ $k$ vértices, todos de grado $2$.
• $G$ está conectado, con un vértice de grado $k \ge 3$, y todos los otros vértices de grado $1$.
• $G$ es un árbol binario tal que, todos los nodos hoja tienen distancia $k$ desde la raíz. Claramente, si $k$ es demasiado grande, no habrá ninguna tales subdiagramas de $K_n$. Cómo de grande puede $k$?

Algunos de los anteriores va a ser fácil; algunos menos.