Les graphes (−2)-monohémimorphes

RésuméNous considérons des graphes finis, simples et non orientés. Le complément dʼun graphe G est le graphe dont les sommets sont ceux de G et tel que deux sommets sont adjacents dans lorsquʼils ne le sont pas dans G. Un graphe est dit auto-complémentaire sʼil est isomorphe à son complément. Deux graphes G et H sont hémimorphes si G est isomorphe à H ou à . Un graphe G à n sommets est (−2)-monohémimorphe si tous ses sous-graphes induits à n−2 sommets sont hémimorphes. Nous montrons que les seuls graphes (−2)-monohémimorphes dʼau moins 5 sommets sont les graphes complets, vides et les graphes arête-transitifs et auto-complémentaires.

We consider only finite, simple and undirected graphs. The complement of a graph G is the graph having the same vertices as G and such that two vertices are adjacent in when they are not in G. A graph is self-complementary if it is isomorphic to its complement. Two graphs G and H are hemimorphic if G is isomorphic to H or to . A graph G on n vertices is (−2)-monohemimorphic if all its induced subgraphs on n−2 vertices are hemimorphic. We prove that the only (−2)-monohemimorphic graphs with at least 5 vertices are the complete graphs, the empty graphs and the graphs which are edge-transitive and self-complementary.