La conjecture de reconstruction dit que les graphes (avec au moins trois sommets) sont déterminés uniquement par leurs sous-graphes supprimés par les sommets. Cette conjecture a cinq décennies.
En recherchant dans la littérature pertinente, j'ai trouvé que les classes de graphiques suivantes sont connues pour être reconstructibles:
- des arbres
- graphes déconnectés, graphes dont le complément est déconnecté
- graphiques réguliers
- Graphiques extra-planaires maximaux
- graphes planaires maximaux
- graphiques externes
- Blocs critiques
- Graphes séparables sans sommets d'extrémité
- graphiques unicycliques (graphiques à un cycle)
- graphiques de produits cartésiens non triviaux
- carrés d'arbres
- graphiques bidegreed
- graphiques d'intervalle unitaire
- graphiques de seuil
- graphiques presque acycliques (c'est-à-dire que Gv est acyclique)
- graphiques de cactus
- graphiques pour lesquels l'un des graphes supprimés est une forêt.
J'ai récemment prouvé qu'un cas particulier de 2 arbres partiels est reconstructible. Je me demande si les 2 arbres partiels (aka graphes série-parallèles ) sont connus pour être reconstructibles. Les arbres partiels ne semblent appartenir à aucune des catégories susmentionnées.
- Est-ce que je manque d'autres classes connues de graphes reconstructibles dans la liste ci-dessus?
- En particulier, les 2 arbres partiels sont-ils connus pour être reconstructibles?
reference-request
graph-theory
co.combinatorics
treewidth
Shiva Kintali
la source
la source
Réponses:
Je crois qu'il n'a pas été démontré que les graphes bidegreed sont reconstructibles. Les graphes bidegreed sont reconstructibles par les bords. Kocay a fait un certain travail sur la reconstruction des graphes bidegreed, mais n'a pas atteint un résultat complet que j'ai pu trouver. L'idée selon laquelle il a été prouvé que les graphiques intégrés sont reconstructibles semble être un peu de désinformation circulant sur le Web.
la source