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

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.)

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).

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.