Comptes Rendus
no. 15-16
Combinatoire
Les graphes (−2)-monohémimorphes

Présenté par : le Comité de rédaction

Badr Boushabi1 ; Abderrahim Boussaïri1
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
Comptes Rendus. Mathématique, Volume 350 (2012) no. 15-16, pp. 731-735.

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 à 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 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 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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2012.09.009
Badr Boushabi 1 ; Abderrahim Boussaïri 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 = {Badr Boushabi and Abderrahim Boussa{\"\i}ri},
     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},
}
TY  - JOUR
AU  - Badr Boushabi
AU  - Abderrahim Boussaïri
TI  - Les graphes (−2)-monohémimorphes
JO  - Comptes Rendus. Mathématique
PY  - 2012
SP  - 731
EP  - 735
VL  - 350
IS  - 15-16
PB  - Elsevier
DO  - 10.1016/j.crma.2012.09.009
LA  - fr
ID  - CRMATH_2012__350_15-16_731_0
ER  - 
%0 Journal Article
%A Badr Boushabi
%A Abderrahim Boussaïri
%T Les graphes (−2)-monohémimorphes
%J Comptes Rendus. Mathématique
%D 2012
%P 731-735
%V 350
%N 15-16
%I Elsevier
%R 10.1016/j.crma.2012.09.009
%G fr
%F CRMATH_2012__350_15-16_731_0
Badr Boushabi; Abderrahim Boussaïri. 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. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2012.09.009/

[1] J.L. Berggren An algebraic characterization of finite symmetric tournaments, Bull. Austral. Math. Soc., Volume 6 (1972), pp. 53-59

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

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

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

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

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

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

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

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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

The (⩽6)-half-reconstructibility of digraphs

Jamel Dammak; Baraa Salem

C. R. Math (2014)

Les paires de tournois {−3}-hypomorphes

Mouna Achour; Youssef Boudabbous; Abderrahim Boussaïri

C. R. Math (2012)

Inversion dans les tournois

Houmem Belkhechine; Moncef Bouaziz; Imed Boudabbous; ...

C. R. Math (2010)