Les graphes (−2)-monohémimorphes

Badr Boushabi; Abderrahim Boussaïri

doi:10.1016/j.crma.2012.09.009

Combinatoire

Les graphes (−2)-monohémimorphes

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

Badr Boushabi ¹ ; Abderrahim Boussaïri ¹

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

Résumé
Abstract

Nous considérons des graphes finis, simples et non orientés. Le complément dʼun graphe G est le graphe $\bar{G}$ dont les sommets sont ceux de G et tel que deux sommets sont adjacents dans $\bar{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 à $\bar{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 $\bar{G}$ having the same vertices as G and such that two vertices are adjacent in $\bar{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 $\bar{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 : 2012-05-08
Accepté le : 2012-09-14
Publié le : 2012-08-01

DOI : 10.1016/j.crma.2012.09.009

Affiliations des auteurs :

Badr Boushabi ¹ ; Abderrahim Boussaïri ¹

¹ 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/

Bibliographie
Cité par

[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