La source du graphe de décomposition modulaire

9

Lors de l'introduction de la décomposition modulaire des graphes , la plupart des auteurs utilisent le graphe à 11 sommets, que je copie de wikipedia.

La question est de savoir qui en est le concepteur d'origine. (Je ne demande pas qui a dessiné ce graphique pour wikipedia, mais la source originale de celui-ci.)

entrez la description de l'image ici

La page wikipedia a été créée en décembre 2006. La première source que je peux trouver est la thèse d'habilitation de Christophe Paul datée du 17 mai 2006. (Je n'ai pas cherché intensivement.)

reference-request graph-theory Yixin Cao
la source
6
Philippe Gambette (qui a créé la page wikipedia) était un doctorant de Christophe Paul. Le mieux est que vous contactiez l'un d'eux, igm.univ-mlv.fr/~gambette ou lirmm.fr/~paul
Louis Esperet

Réponses:

7

Sur proposition de Louis Esperet, j'ai contacté Philippe Gambette et Christophe Paul, qui m'ont rapidement confirmé. Paul a conçu ce graphique pour sa thèse d'habilitation. Lorsqu'ils ont créé une page Wikipedia pour la décomposition modulaire, ils ont utilisé ce graphique. C'est peut-être le début de sa large adaptation. Il figure également dans l'enquête bien connue de Michel Habib et Christophe Paul (DOI: 10.1016 / j.cosrev.2010.01.001).

Quelques belles propriétés de ce graphique:

  • c'est un graphe de permutation
  • son nœud principal (le taureau) est un graphe premier contenant un sommet qui évite tout P4 induit. Lorsqu'un tel nœud existe, il est unique.
Yixin Cao
la source