Die Quelle des modularen Zerlegungsgraphen

9

Bei der Einführung der modularen Zerlegung von Graphen verwenden die meisten Autoren den 11-Vertex-Graphen, den ich aus Wikipedia kopiere.

Die Frage ist, wer der ursprüngliche Designer davon ist (sind). (Ich frage nicht, wer diese Grafik für Wikipedia gezeichnet hat, sondern die ursprüngliche Quelle.)

Geben Sie hier die Bildbeschreibung ein

Die Wikipedia-Seite wurde im Dezember 2006 erstellt. Die früheste Quelle, die ich finden kann, ist die Habilitationsthese von Christophe Paul vom 17. Mai 2006. (Ich habe nicht intensiv gesucht.)

reference-request graph-theory Yixin Cao
quelle
6
Philippe Gambette (der die Wikipedia-Seite erstellt hat) war ein Doktorand von Christophe Paul. Das Beste ist, dass Sie entweder einen von ihnen kontaktieren , igm.univ-mlv.fr/~gambette oder lirmm.fr/~paul
Louis Esperet

Antworten:

7

Auf Vorschlag von Louis Esperet kontaktierte ich Philippe Gambette und Christophe Paul, die dies umgehend bestätigten. Paul entwarf diese Grafik für seine Habilitationsarbeit. Als sie eine Wikipedia-Seite für die modulare Zerlegung erstellten, verwendeten sie dieses Diagramm. Vielleicht ist es der Beginn seiner umfassenden Anpassung. Es ist auch in der bekannten Umfrage von Michel Habib und Christophe Paul (DOI: 10.1016 / j.cosrev.2010.01.001) enthalten.

Einige nette Eigenschaften dieses Diagramms sind:

  • Es ist ein Permutationsgraph
  • Sein Hauptknoten (der Bulle) ist ein Hauptgraph, der einen Scheitelpunkt enthält, der jedes induzierte P4 vermeidet. Wenn ein solcher Knoten vorhanden ist, ist er eindeutig.
Yixin Cao
quelle