Гипотеза реконструкции говорит о том, что графы (по крайней мере, с тремя вершинами) определяются однозначно их вершинами удаленных подграфов. Этой гипотезе пять десятилетий.
В поисках соответствующей литературы я обнаружил, что следующие классы графов, как известно, восстанавливаемы:
- деревья
- несвязные графы, графы, дополнение которых несвязно
- регулярные графики
- Максимальные Внешние Планарные Графики
- максимальные плоские графы
- внешнепланарные графики
- Критические блоки
- Разделимые графы без конечных вершин
- унициклические графы (графы с одним циклом)
- нетривиальные графики декартовых произведений
- квадраты деревьев
- двуглавые графы
- графики единичных интервалов
- пороговые графики
- почти ациклические графы (т.е. Gv ацикличен)
- графы кактусов
- графы, для которых один из удаленных вершин графа является лесом.
Недавно я доказал, что частный случай частичных 2-деревьев восстанавливаем. Мне интересно, если известно, что частичные 2-деревья (или параллельно-последовательные графы ) восстанавливаемы. Частичные 2-деревья, по-видимому, не попадают ни в одну из вышеупомянутых категорий.
- Я пропускаю какие-либо другие известные классы восстанавливаемых графов в приведенном выше списке?
- В частности, известно ли, что частичные 2-деревья восстанавливаемы?
reference-request
graph-theory
co.combinatorics
treewidth
Шива Кинтали
источник
источник
Ответы:
Я полагаю, что не было показано, что двунитевые графы восстанавливаемы. Двунаправленные графы восстанавливаемы по ребрам. Kocay проделал некоторую работу по восстановлению двунаправленных графов, но не достиг всеобъемлющего результата, который мне удалось найти. Представление о том, что доказано, что двунаправленные графы восстанавливаемы, похоже, представляет собой некоторую дезинформацию, циркулирующую в сети.
источник