La conjetura de reconstrucción dice que los gráficos (con al menos tres vértices) están determinados únicamente por sus subgrafos eliminados de vértices. Esta conjetura tiene cinco décadas.
Al buscar literatura relevante, descubrí que se sabe que las siguientes clases de gráficos son reconstruibles:
- arboles
- gráficos desconectados, gráficos cuyo complemento está desconectado
- gráficos regulares
- Gráficos del plano exterior máximo
- gráficos planos máximos
- gráficos del plano exterior
- Bloques críticos
- Gráficos separables sin vértices finales
- gráficos unicíclicos (gráficos con un ciclo)
- gráficos de productos cartesianos no triviales
- cuadrados de arboles
- gráficos de bidegreed
- gráficos de intervalos unitarios
- gráficos de umbral
- gráficos casi acíclicos (es decir, Gv es acíclico)
- gráficos de cactus
- gráficos para los cuales uno de los gráficos de vértice eliminado es un bosque.
Recientemente probé que un caso especial de 2 árboles parciales es reconstruible. Me pregunto si se sabe que los árboles parciales parciales (también conocidos como gráficos en serie y paralelos ) son reconstruibles. Los 2 árboles parciales no parecen caer en ninguna de las categorías mencionadas anteriormente.
- ¿Me estoy perdiendo otras clases conocidas de gráficos reconstructibles en la lista anterior?
- En particular, ¿se sabe que los árboles parciales 2 son reconstruibles?
reference-request
graph-theory
co.combinatorics
treewidth
Shiva Kintali
fuente
fuente
Respuestas:
Creo que no se ha demostrado que los gráficos bidegreed sean reconstruibles. Los gráficos bidegreed son reconstruibles por los bordes Kocay trabajó un poco en la reconstrucción de gráficos bidegreed, pero no alcanzó un resultado completo que pude encontrar. La noción de que se ha demostrado que los gráficos bidegreed son reconstruibles parece ser un poco de información errónea que circula en la web.
fuente