Przypuszczenie o rekonstrukcji mówi, że wykresy (z co najmniej trzema wierzchołkami) są określane jednoznacznie przez ich podgrupy usunięte z wierzchołków. Ta hipoteza ma pięć dekad.
Przeszukując odpowiednią literaturę, odkryłem, że następujące klasy grafów są rekonstruowalne:
- drzewa
- wykresy odłączone, wykresy, których dopełnienie jest odłączone
- regularne wykresy
- Maksymalne wykresy zewnętrzne
- maksymalne wykresy płaskie
- wykresy zewnętrzne
- Krytyczne bloki
- Oddzielne wykresy bez wierzchołków końcowych
- wykresy jednopierścieniowe (wykresy z jednym cyklem)
- nietrywialne kartezjańskie wykresy produktów
- kwadraty drzew
- wykresy bidegreed
- wykresy interwałów jednostkowych
- wykresy progowe
- wykresy prawie acykliczne (tzn. Gv jest acykliczna)
- wykresy kaktusów
- wykresy, dla których jednym z usuniętych wierzchołków jest las.
Niedawno udowodniłem, że szczególny przypadek częściowych 2-drzew można odtworzyć. Zastanawiam się, czy częściowe 2-drzewa ( znane również jako wykresy szeregowo-równoległe ) są znane z możliwości odtworzenia. Częściowe 2-drzewa nie wydają się należeć do żadnej z wyżej wymienionych kategorii.
- Czy brakuje mi innych znanych klas grafów odtwarzalnych na powyższej liście?
- W szczególności, czy częściowe 2-drzewa są znane z możliwości odtworzenia?
reference-request
graph-theory
co.combinatorics
treewidth
Shiva Kintali
źródło
źródło
Odpowiedzi:
Uważam, że nie wykazano, że wykresy z licytacji są odtwarzalne. Wykresy Bidegreed można odtworzyć na krawędziach. Kocay popracował trochę nad rekonstrukcją grafów bidegreed, ale nie osiągnął kompleksowego rezultatu, który udało mi się znaleźć. Pogląd, że udowodniono, że wykresy z licytacji są rekonstruowalne, wydaje się być nieco dezinformacją krążącą w sieci.
źródło