Hipoteza odbudowy i częściowe 2-drzewa

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?

— Shiva Kintali
źródło

Nie mam do niego dostępu, ale ten artykuł: springerlink.com/content/p6r03877310411wr twierdzi, że uporządkowane zestawy wolne od N można odtworzyć.

— mhum

W celu dalszego rozwinięcia komentarza @ mhum: częściowe szeregi równoległe szeregowo są dokładnie tymi, które są wolne od N, więc w artykule twierdzi się, że zbiory szeregowe równoległe są odtwarzalne. Przechodnie redukcje zestawów szeregowo-równoległych są wykresami szeregowo-równoległymi, ale nie jestem pewien, w jaki sposób domysł rekonstrukcji oddziałuje z krawędziami przechodnimi.

— András Salamon

Dla twojej listy: Kiyomi, Saitoh i Uehara wykazali, że wykresy dwustronnej permutacji są możliwe do odtworzenia .

— Yota Otachi

Jeszcze jedna dla twojej listy: niektóre wykresy płaskie można odtworzyć .

— virgi

Shiva, dostałeś jakiś nowy wynik?

— Saeed

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.

— MattM
źródło