Necesito un par de grafos no isomórficos con la menor posibilidad de n vértices y en los que las secuencias de grados sean iguales. ¿El número mínimo es 2, como un multigrafo con n=2? Por favor, ayuda con el razonamiento de esta pregunta. Gracias.
Respuesta
¿Demasiados anuncios?
Para $n=5$ Hay tres pares de simple gráficos que tienen la misma secuencia de grados:
- El grafo bipartito completo $K_{2,3}$ y el gráfico de la casa .
- El camino $P_5$ y la unión disjunta $K_3 + K_2$ .
- El gráfico de los renacuajos $T_{4,1}$ y el gráfico de los renacuajos $T_{3,2}$ .
Para $n=4$ no hay gráficos sencillos que funcionen (lo que podemos verificar comprobando todos los $11$ posibilidades). Si los multigrafos sin bucles son un juego limpio, entonces el ciclo $C_4$ puede confundirse con la unión disjunta de dos grafos digon (donde un grafo digon tiene dos vértices con dos copias de la arista entre ellos); también existen otros ejemplos.
Para $n=3$ y por debajo, ni siquiera los bordes paralelos ayudan. En el $n=1$ caso, sólo hay un multigrafo sin bucles. En el $n=2$ nuestra única libertad es elegir el número de aristas entre los dos vértices, y ese número de aristas también nos indica el grado de cada vértice. En el $n=3$ caso, si la secuencia de grados es $d_1, d_2, d_3$ y hay $m_{ij}$ aristas entre vértices $i$ y $j$ entonces tenemos el sistema de ecuaciones \begin{align} d_1 &= m_{12} + m_{13} \\ d_2 &= m_{12} + m_{23} \\ d_3 &= m_{13} + m_{23} \end{align} y esto tiene una solución única cuando $d_1, d_2, d_3$ son fijos: $$(m_{12}, m_{13}, m_{23}) = \left(\frac{d_1 + d_2 - d_3}{2},\frac{d_1 - d_2 + d_3}{2},\frac{-d_1 + d_2 + d_3}{2}\right).$$ Por lo tanto, sólo hay un multigrafo sin bucles con cada secuencia de grados. (Algunas secuencias de grados no producirán ningún multigrafo sin bucles, si los grados son Impares, o si un grado supera la suma de los otros dos).
