¿Hay alguna forma de averiguar el número total de gráficos simples de una secuencia dada?

Question

Este problema vino a mi mente al azar mientras estudiaba la teoría de los gráficos. Supongamos que 3,3,3,3,3,3 es una secuencia dada del grado de vértices de un gráfico. Sabemos que uno de sus gráficos es un hexágono con diagonales opuestas adjuntas. Pero supongamos que se da una secuencia arbitraria y supongamos que se garantiza que existe una gráfica, entonces cómo encontrar todas esas gráficas (quiero decir, ¿hay algún algoritmo o tenemos que encontrar esas gráficas al azar)?

Answer 1

Usted puede, de hecho. Hay un artículo sobre ello aquí :

Zoltán Király "Reconociendo gráfico grado de secuencias y de la generación de todas las realizaciones"

Tenga en cuenta que este enfoque va a la lista de varias isomorfo copias de los gráficos de una secuencia, es decir, que es redundante, pero la lista de todos ellos (es exhaustiva).

Gracias a Pedro Erdos, que me señaló a este periódico.