Si dos grafos tienen el mismo número de árboles de cada tipo, ¿deben ser isomorfos?

Question

Preparados. Sea $G$ sea un grafo (simple). Dado un árbol $T$ definamos: $$ a_{T}(G) = \text{number of subgraphs of } G \text{ that are isomorphic to } T $$ Si $T$ y $T'$ son isomorfas, entonces por supuesto $a_{T}(G)=a_{T'}(G)$ . Por lo tanto, sólo tenemos que considerar las clases de isomorfismo de los árboles al definir este invariante.

Pregunta. Supongamos que $G$ y $H$ son dos gráficos. Supongamos que $a_{T}(G)=a_{T}(H)$ es válido para cada árbol $T$ . ¿Se deduce que $G$ y $H$ son isomorfas?

Contexto. Las invariantes básicas de $G$ son el número de vértices y el número de aristas. Dado que los vértices pueden considerarse árboles (es decir, un árbol con 1 vértice) y las aristas también pueden considerarse árboles (es decir, un árbol con 2 vértices), uno se inclina a contar otros tipos de árboles contenidos en $G$ . Es de esperar que esto motive el problema anterior.

Observación. He decidido incluir la etiqueta [examples-counterexamples], por si acaso mi pregunta tiene una respuesta negativa. Si es así, me encantaría ver un contraejemplo explícito que incluya un par de grafos no isomorfos que compartan esta invariante para todos los árboles.

Answer 1

Contraejemplo:

En primer lugar, tenga en cuenta que $a_T(G_1) + a_T(G_2) = a_T(G_1\sqcup G_2)$ .

En segundo lugar, obsérvese que los únicos subárboles de los grafos de ciclos y los grafos de caminos son los caminos. Si $G$ es un camino o ciclo, la lista completa de árboles contenidos en $G$ se encuentra, por tanto, en $\{P_1, \dots, P_{|V(G)|}\}.$ Por tanto, podemos identificar un gráfico de ciclo o trayectoria $G$ con un vector $v_G = (a_1,\dots, a_n)$ donde $a_i = a_{P_i}(G)$ y $n = |V(G)|$ . Tenga en cuenta que $v_{P_1} = (1,0, 0), v_{P_2} = (2,1, 0),v_{P_3} = (3, 2, 1)$ , $v_{C_3} = (3,3,3)$ . Estos vectores son linealmente dependientes; en particular, $3v_{P_2} + v_{C_3} = 3v_{P_3}$ . De ello se deduce que $P_2^{\sqcup 3}\sqcup C_3$ y $P_3^{\sqcup 3}$ tienen los mismos conjuntos múltiples de árboles, pero estos dos grafos tienen un número diferente de componentes conectados.

En general, se pueden construir más contraejemplos considerando uniones disjuntas de grafos de caminos y grafos de ciclos, ya que hay $2n-2$ caminos/ciclos a elegir entre los grafos cuyos únicos subárboles son $P_1,\dots, P_n$ .

Estos contraejemplos quedan completamente arruinados si, en lugar de contar subárboles, contamos subbosques. Tal vez esta conjetura pueda demostrarse si en lugar de eso consideramos los subárboles, aunque me pregunto si surgirá un problema similar: tal vez haya demasiados grafos y no suficientes bosques para que los conjuntos múltiples sean todos distintos.

Edición: accidentalmente escribí $P_2$ en lugar de $P_3$ en algunos lugares.