Sumber grafik dekomposisi modular

9

Ketika memperkenalkan grafik dekomposisi modular , kebanyakan penulis menggunakan grafik 11-simpul, yang saya salin dari wikipedia.

Pertanyaannya adalah siapa desainer asli dari itu. (Saya tidak bertanya siapa yang menggambar grafik ini untuk wikipedia, tetapi sumber aslinya).

masukkan deskripsi gambar di sini

Halaman wikipedia dibuat pada Desember 2006. Sumber paling awal yang dapat saya temukan adalah tesis Habilitasi Christophe Paul tertanggal 17 Mei 2006. (Saya tidak mencari secara intensif.)

reference-request graph-theory Yixin Cao
sumber
6
Philippe Gambette (yang membuat halaman wikipedia) adalah seorang mahasiswa PhD Christophe Paul. Yang terbaik adalah Anda menghubungi salah satu dari mereka, igm.univ-mlv.fr/~gambette atau lirmm.fr/~paul
Louis Esperet

Jawaban:

7

Atas saran Louis Esperet, saya menghubungi Philippe Gambette dan Christophe Paul, yang segera dikonfirmasi. Paul merancang grafik ini untuk tesis Habilitasi. Ketika mereka membuat halaman Wikipedia untuk dekomposisi modular, mereka menggunakan grafik ini. Mungkin ini awal dari adaptasinya yang luas. Ini juga ditampilkan dalam survei terkenal Michel Habib dan Christophe Paul (DOI: 10.1016 / j.cosrev.2010.01.001).

Beberapa properti grafik ini termasuk:

  • ini adalah grafik permutasi
  • simpul utamanya (bull) adalah grafik utama yang berisi simpul yang menghindari setiap P4 yang diinduksi. Ketika ada simpul seperti itu, itu unik.
Yixin Cao
sumber