9
$\begingroup$

When introducing graph modular decomposition, most authors use the 11-vertex graph, which I copy from wikipedia.

The question is who is (are) the original designer of it. (I'm not asking who drew this graph for wikipedia, but the original source of it.)

enter image description here

The wikipedia page was created in December 2006. The earliest source I can find is the Habilitation thesis of Christophe Paul dated on May 17, 2006. (I didn't search intensively.)

Improve this question
$\endgroup$
1
7
$\begingroup$

Upon the suggestion of Louis Esperet, I contacted Philippe Gambette and Christophe Paul, who confirmed promptly. Paul designed this graph for his Habilitation thesis. When they created a Wikipedia page for modular decomposition, they used this graph. Maybe it's the beginning of its wide adaption. It's also featured in the well known survey of Michel Habib and Christophe Paul (DOI:10.1016/j.cosrev.2010.01.001).

Some nice properties of this graph include:

  • it is a permutation graph
  • its prime node (the bull) is a prime graph containing a vertex that avoids every induced P4. When such a node exists, it is unique.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.