Źródło modułowego wykresu rozkładu

9

Podczas wprowadzania modularnego rozkładu grafów większość autorów używa wykresu 11-wierzchołkowego, który kopiuję z wikipedii.

Pytanie brzmi, kto jest (są) jego oryginalnymi projektantami. (Nie pytam, kto narysował ten wykres dla wikipedii, ale oryginalne źródło.)

wprowadź opis zdjęcia tutaj

Strona wikipedia została utworzona w grudniu 2006 r. Najwcześniejsze źródło, jakie mogę znaleźć, to teza habilitacyjna Christophe Paul z 17 maja 2006 r. (Nie szukałem intensywnie).

reference-request graph-theory Yixin Cao
źródło
6
Philippe Gambette (który stworzył stronę wikipedii) był doktorantem Christophe Paul. Najlepiej jest skontaktować się z jednym z nich, igm.univ-mlv.fr/~gambette lub lirmm.fr/~paul
Louis Esperet

Odpowiedzi:

7

Za sugestią Louisa Espereta skontaktowałem się z Philippe'em Gambette i Christophe Paulem, który szybko to potwierdził. Paul zaprojektował ten wykres do swojej pracy habilitacyjnej. Kiedy utworzyli stronę w Wikipedii dla modułowego rozkładu, użyli tego wykresu. Może to początek jego szerokiej adaptacji. Jest również opisywany w dobrze znanej ankiecie Michela Habiba i Christophe Paul (DOI: 10.1016 / j.cosrev.2010.01.001).

Niektóre ładne właściwości tego wykresu to:

  • jest to wykres permutacji
  • jego główny węzeł (byk) jest pierwszym wykresem zawierającym wierzchołek, który unika każdego indukowanego P4. Gdy taki węzeł istnieje, jest unikalny.
Yixin Cao
źródło