Combinatoire
Les graphes (−2)-monohémimorphes
[(2)-monohemimorphic graphs]
Comptes Rendus. Mathématique, Volume 350 (2012) no. 15-16, pp. 731-735.

We consider only finite, simple and undirected graphs. The complement of a graph G is the graph G¯ having the same vertices as G and such that two vertices are adjacent in G¯ 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 H¯. A graph G on n vertices is (2)-monohemimorphic if all its induced subgraphs on n2 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.

Nous considérons des graphes finis, simples et non orientés. Le complément dʼun graphe G est le graphe G¯ dont les sommets sont ceux de G et tel que deux sommets sont adjacents dans G¯ 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 à H¯. Un graphe G à n sommets est (2)-monohémimorphe si tous ses sous-graphes induits à n2 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.

Received:
Accepted:
Published online:
DOI: 10.1016/j.crma.2012.09.009
Boushabi, Badr 1; Boussaïri, Abderrahim 1

1 Faculté des sciences Aïn-Chock, département de mathématiques et informatique, Km 8 route dʼEl Jadida, BP 5366 Maarif, Casablanca, Maroc
@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, Volume 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] Berggren, J.L. An algebraic characterization of finite symmetric tournaments, Bull. Austral. Math. Soc., Volume 6 (1972), pp. 53-59

[2] Boudabbous, Y. Reconstructible and half-reconstructible tournaments: application to their groups of hemimorphisms, MLQ Math. Log. Q., Volume 45 (1999) no. 3, pp. 421-431

[3] Bondy, J.A.; Murty, U.S.R. Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976 (x+264 pp)

[4] Fraïssé, R. Theory of Relations, North-Holland Publ. Co., Amsterdam, 1986

[5] Goodman, A.W. On sets of acquaintances and strangers at any party, Amer. Math. Monthly, Volume 66 (1959), pp. 778-783

[6] Jean, M. Line-symmetric tournaments, Recent Progress in Combinatorics, Academic Press, New York, 1969, pp. 265-271

[7] Kantor, W.M. Automorphism groups of designs, Math. Z., Volume 109 (1969), pp. 246-252

[8] Peisert, W. All self-complementary symmeric graphs, J. Algebra, Volume 240 (2001), pp. 209-229

[9] Pouzet, M. Sur certains tournois reconstructibles. Applications à leurs groupes dʼautomorphismes, Discrete Math., Volume 24 (1978), pp. 225-229

Cited by Sources: