8 votos

Encuentra todos los dibujos buenos no isomórficos de $K_{3,3}$ ?

A veces miro todos los dibujos buenos no isomórficos de gráficos en un plano o esfera.

Buen dibujo significa que ninguna arista se cruza a sí misma, que no hay dos aristas que se crucen más de una vez y que no hay dos aristas incidentes con el mismo vértice que se crucen entre sí.

No isomorfo significa que no hay isomorfismo de los dibujos como grafos incrustados.

Mis preguntas son:

¿Cuántos buenos dibujos hay de $K_{3,3}$ ?

¿Existe algún sitio web o programa que enumere todos los buenos dibujos de gráficos con un máximo de $n$ ¿Vértices?

A continuación se ilustran los tres requisitos de un buen gráfico: enter image description here

Para los gráficos pequeños, se obtienen los siguientes resultados.

Para los grafos completos con un máximo de 5 vértices, la lista de buenos dibujos está básicamente clara. También están resumidos en el libro de Marcus Sahefer sobre Cruce de números de gráficos (CRC Press, 2018):

  • Hay dos buenos dibujos no isomórficos de $K_4$ en la esfera.
  • Hay cinco dibujos no isomórficos de $K_5$ en la esfera.

Mientras tanto, $K_{2,3}$ tiene $4$ buenos dibujos, como se describe en Michal Stas, "Join Products [K. sub. 2, 3]+[C. sub. n]" ( Matemáticas v8.6, 2020). Se ilustran en el siguiente gráfico:

enter image description here

Podemos obtener listas de grafos no isomórficos en sitios web (por ejemplo http://users.cecs.anu.edu.au/~bdm/data/graphs.html ) o de programas informáticos como maple o geng. ¿Cómo podemos obtener una lista similar de dibujos buenos no isomórficos?

5voto

Gopi Flaherty Puntos 61

La lista de dibujos buenos no isomórficos de $K_{m,n}$ con $2\le m,n \le 3$ aparece en el siguiente documento:

Heiko Harborth, Paridad de números de cruces para grafos completos n-partitos, Mathematica Slovaca, Vol. 26 (1976), No. 2, 77-95. URL persistente: http://dml.cz/dmlcz/136111

El número de dibujos buenos no isomórficos de $K_{3,3}$ obtenido es $102$ .

Para $K_{2,3}$ Hay seis dibujos no isomórficos. Los dos que faltan en la figura 1 a la que se hace referencia en la pregunta pueden no ser realizables con aristas rectilíneas.

La lista de buenos dibujos no isomórficos de grafos con hasta cinco vértices aparece en el documento

H-D. O. F. Gronau y H. Harborth, Números de dibujos no isomórficos para grafos pequeños, Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989). Congr. Numer. 71 (1990), 105-114.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X