La fuente del gráfico de descomposición modular.

Al presentar la descomposición modular del gráfico , la mayoría de los autores utilizan el gráfico de 11 vértices, que copio de wikipedia.

La pregunta es quién es (son) el diseñador original de la misma. (No estoy preguntando quién dibujó este gráfico para Wikipedia, sino la fuente original del mismo).

La página de Wikipedia fue creada en diciembre de 2006. La fuente más antigua que puedo encontrar es la tesis de Habilitación de Christophe Paul, fechada el 17 de mayo de 2006. (No busqué intensamente).

A sugerencia de Louis Esperet, me puse en contacto con Philippe Gambette y Christophe Paul, quienes confirmaron rápidamente. Paul diseñó este gráfico para su tesis de Habilitación. Cuando crearon una página de Wikipedia para descomposición modular, usaron este gráfico. Tal vez sea el comienzo de su amplia adaptación. También aparece en la conocida encuesta de Michel Habib y Christophe Paul (DOI: 10.1016 / j.cosrev.2010.01.001).

Algunas buenas propiedades de este gráfico incluyen:

• es un gráfico de permutación
• su nodo principal (el toro) es un gráfico principal que contiene un vértice que evita cada P4 inducido. Cuando existe tal nodo, es único.