Dugaan rekonstruksi mengatakan bahwa grafik (dengan setidaknya tiga simpul) ditentukan secara unik oleh subgraf yang dihapus dari verteks. Dugaan ini berusia lima dekade.
Mencari literatur yang relevan, saya menemukan bahwa kelas grafik berikut diketahui dapat direkonstruksi:
- pohon
- grafik terputus, grafik yang komplemennya terputus
- grafik reguler
- Grafik Outerplanar Maksimal
- grafik planar maksimal
- grafik outerplanar
- Blok kritis
- Grafik yang dapat dipisahkan tanpa simpul ujung
- grafik unicyclic (grafik dengan satu siklus)
- grafik produk kartesian non-sepele
- kotak pohon
- grafik bidegreed
- grafik satuan interval
- grafik ambang batas
- grafik hampir asiklik (yaitu, Gv asiklik)
- grafik kaktus
- grafik yang salah satu dari grafik simpul yang dihapus adalah hutan.
Baru-baru ini saya membuktikan bahwa kasus khusus 2-pohon parsial dapat direkonstruksi. Saya bertanya-tanya apakah parsial 2-pohon (alias seri-paralel grafik ) diketahui dapat direkonstruksi. Parsial 2-pohon tampaknya tidak termasuk dalam kategori yang disebutkan di atas.
- Apakah saya melewatkan kelas-kelas lain dari grafik yang dapat direkonstruksi dalam daftar di atas?
- Secara khusus, apakah parsial 2-pohon diketahui dapat direkonstruksi?
reference-request
graph-theory
co.combinatorics
treewidth
Siwa Kintali
sumber
sumber
Jawaban:
Saya percaya bahwa belum ditunjukkan bahwa grafik bidegreed dapat direkonstruksi. Grafik bidegreed dapat direkonstruksi tepi. Kocay melakukan beberapa pekerjaan pada rekonstruksi grafik bidegreed, tetapi tidak mencapai hasil komprehensif yang saya dapat temukan. Gagasan bahwa telah terbukti bahwa grafik bidegreed dapat direkonstruksi tampaknya sedikit informasi yang salah yang beredar di web.
sumber