A fonte do gráfico de decomposição modular

9

Ao introduzir a decomposição modular do gráfico , a maioria dos autores usa o gráfico de 11 vértices, que eu copio da wikipedia.

A questão é quem é (é) o criador original dele. (Não estou perguntando quem desenhou este gráfico para a wikipedia, mas a fonte original dele.)

insira a descrição da imagem aqui

A página da wikipedia foi criada em dezembro de 2006. A fonte mais antiga que posso encontrar é a tese de Habilitação de Christophe Paul, datada de 17 de maio de 2006. (não procurei intensamente.)

reference-request graph-theory Yixin Cao
fonte
6
Philippe Gambette (que criou a página da wikipedia) era um estudante de doutorado de Christophe Paul. O melhor é que você entre em contato com qualquer um deles, igm.univ-mlv.fr/~gambette ou lirmm.fr/~paul
Louis Esperet

Respostas:

7

Por sugestão de Louis Esperet, entrei em contato com Philippe Gambette e Christophe Paul, que confirmaram prontamente. Paulo projetou este gráfico para sua tese de Habilitação. Quando eles criaram uma página da Wikipedia para decomposição modular, eles usaram esse gráfico. Talvez seja o começo de sua ampla adaptação. Também aparece na bem conhecida pesquisa de Michel Habib e Christophe Paul (DOI: 10.1016 / j.cosrev.2010.01.001).

Algumas boas propriedades deste gráfico incluem:

  • é um gráfico de permutação
  • seu nó primo (o touro) é um gráfico primo contendo um vértice que evita todos os P4 induzidos. Quando esse nó existe, é único.
Yixin Cao
fonte