A conjectura de reconstrução diz que os gráficos (com pelo menos três vértices) são determinados exclusivamente por seus subgrafos deletados. Essa conjectura tem cinco décadas.
Pesquisando literatura relevante, descobri que as seguintes classes de gráficos são conhecidas por serem reconstrutíveis:
- árvores
- gráficos desconectados, gráficos cujo complemento está desconectado
- gráficos regulares
- Gráficos Outplanplanares máximos
- gráficos planares máximos
- gráficos externos
- Blocos críticos
- Gráficos separáveis sem vértices finais
- gráficos unicíclicos (gráficos com um ciclo)
- gráficos cartesianos não triviais de produtos
- quadrados de árvores
- gráficos bidirecionais
- gráficos de intervalo de unidades
- gráficos de limiar
- gráficos quase acíclicos (ou seja, Gv é acíclico)
- gráficos de cactos
- gráficos para os quais um dos gráficos excluídos do vértice é uma floresta.
Recentemente, provei que um caso especial de 2 árvores parciais é reconstrutível. Gostaria de saber se 2-árvores parciais (também conhecidas como gráficos paralelos em série ) são conhecidas por serem reconstrutíveis. As 2 árvores parciais não parecem se encaixar em nenhuma das categorias mencionadas acima.
- Estou perdendo outras classes conhecidas de gráficos reconstrutíveis na lista acima?
- Em particular, as 2 árvores parciais são conhecidas por serem reconstrutíveis?
reference-request
graph-theory
co.combinatorics
treewidth
Shiva Kintali
fonte
fonte
Respostas:
Eu acredito que não foi demonstrado que os gráficos bidegreed são reconstrutíveis. Os gráficos bidegreed são reconstrutíveis pela borda. Kocay fez um trabalho de reconstrução de gráficos bidirecionais, mas não alcançou um resultado abrangente que consegui encontrar. A noção de que foi provado que os gráficos bidirecionais são reconstrutíveis parece ser um pouco de desinformação circulando na web.
fonte