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 -monohémimorphe si tous ses sous-graphes induits à sommets sont hémimorphes. Nous montrons que les seuls graphes -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 -monohemimorphic if all its induced subgraphs on vertices are hemimorphic. We prove that the only -monohemimorphic graphs with at least 5 vertices are the complete graphs, the empty graphs and the graphs which are edge-transitive and self-complementary.
Accepté le :
Publié le :
@article{CRMATH_2012__350_15-16_731_0,
author = {Boushabi, Badr and Boussa{\"\i}ri, Abderrahim},
title = {Les graphes (\ensuremath{-}2)-monoh\'emimorphes},
journal = {Comptes Rendus. Math\'ematique},
pages = {731--735},
publisher = {Elsevier},
volume = {350},
number = {15-16},
year = {2012},
doi = {10.1016/j.crma.2012.09.009},
language = {fr},
url = {http://www.numdam.org/articles/10.1016/j.crma.2012.09.009/}
}
TY - JOUR AU - Boushabi, Badr AU - Boussaïri, Abderrahim TI - Les graphes (−2)-monohémimorphes JO - Comptes Rendus. Mathématique PY - 2012 SP - 731 EP - 735 VL - 350 IS - 15-16 PB - Elsevier UR - http://www.numdam.org/articles/10.1016/j.crma.2012.09.009/ DO - 10.1016/j.crma.2012.09.009 LA - fr ID - CRMATH_2012__350_15-16_731_0 ER -
%0 Journal Article %A Boushabi, Badr %A Boussaïri, Abderrahim %T Les graphes (−2)-monohémimorphes %J Comptes Rendus. Mathématique %D 2012 %P 731-735 %V 350 %N 15-16 %I Elsevier %U http://www.numdam.org/articles/10.1016/j.crma.2012.09.009/ %R 10.1016/j.crma.2012.09.009 %G fr %F CRMATH_2012__350_15-16_731_0
Boushabi, Badr; Boussaïri, Abderrahim. Les graphes (−2)-monohémimorphes. Comptes Rendus. Mathématique, Tome 350 (2012) no. 15-16, pp. 731-735. doi : 10.1016/j.crma.2012.09.009. http://www.numdam.org/articles/10.1016/j.crma.2012.09.009/
[1] An algebraic characterization of finite symmetric tournaments, Bull. Austral. Math. Soc., Volume 6 (1972), pp. 53-59
[2] Reconstructible and half-reconstructible tournaments: application to their groups of hemimorphisms, MLQ Math. Log. Q., Volume 45 (1999) no. 3, pp. 421-431
[3] Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976 (x+264 pp)
[4] Theory of Relations, North-Holland Publ. Co., Amsterdam, 1986
[5] On sets of acquaintances and strangers at any party, Amer. Math. Monthly, Volume 66 (1959), pp. 778-783
[6] Line-symmetric tournaments, Recent Progress in Combinatorics, Academic Press, New York, 1969, pp. 265-271
[7] Automorphism groups of designs, Math. Z., Volume 109 (1969), pp. 246-252
[8] All self-complementary symmeric graphs, J. Algebra, Volume 240 (2001), pp. 209-229
[9] Sur certains tournois reconstructibles. Applications à leurs groupes dʼautomorphismes, Discrete Math., Volume 24 (1978), pp. 225-229
Cité par Sources :
