Comptes Rendus
Logique/Combinatoire
Les graphes critiquement sans duo
Comptes Rendus. Mathématique, Volume 347 (2009) no. 9-10, pp. 463-466.

Soit G=(S,A) un graphe (orienté). Le graphe G est un tournoi si pour x,yS, (x,y)A si et seulement si (y,x)A. À chaque partie X de S est associé le sous-graphe G[X]=(X,(X×X)A) de G induit par X. Une partie I de S est un intervalle de G si pour tous a,bI et xS\I, (a,x)A si et seulement si (b,x)A et (x,a)A si et seulement si (x,b)A. Un duo de G est un intervalle de G à deux éléments. Le graphe G est critiquement sans duo s'il est sans duo et si pour tout xS, le sous-graphe G[S\{x}] admet au moins un duo. Suite à l'étude des tournois acycliques, faite par J.F. Culus et B. Jouve en 2005, nous donnons, dans cette Note, une description morphologique complète des graphes critiquement sans duo.

Let G=(V,A) be a digraph. G is a tournament if for x,yV, (x,y)A if and only if (y,x)A. The induced subgraph of G by a subset X of V is denoted by G[X]. A subset I of V is an interval of G provided that for any a,bI and xV\I, (a,x)A if and only if (b,x)A, and (x,a)A if and only if (x,b)A. An interval of G on 2 elements is called duo of G. G is called critically without duo if it is without duo and for all xV, the subgraph G[V\{x}] has at least one duo. Following the study of acyclic tournaments made by J.F. Culus and B. Jouve in 2005, we give, in this Note, a complete morphologic description of critically without duo graphs.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2009.03.008

Youssef Boudabbous 1 ; Abdeljelil Salhi 2

1 Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie
2 Faculté des sciences de Gafsa, 2112 Gafsa, Tunisie
@article{CRMATH_2009__347_9-10_463_0,
     author = {Youssef Boudabbous and Abdeljelil Salhi},
     title = {Les graphes critiquement sans duo},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {463--466},
     publisher = {Elsevier},
     volume = {347},
     number = {9-10},
     year = {2009},
     doi = {10.1016/j.crma.2009.03.008},
     language = {fr},
}
TY  - JOUR
AU  - Youssef Boudabbous
AU  - Abdeljelil Salhi
TI  - Les graphes critiquement sans duo
JO  - Comptes Rendus. Mathématique
PY  - 2009
SP  - 463
EP  - 466
VL  - 347
IS  - 9-10
PB  - Elsevier
DO  - 10.1016/j.crma.2009.03.008
LA  - fr
ID  - CRMATH_2009__347_9-10_463_0
ER  - 
%0 Journal Article
%A Youssef Boudabbous
%A Abdeljelil Salhi
%T Les graphes critiquement sans duo
%J Comptes Rendus. Mathématique
%D 2009
%P 463-466
%V 347
%N 9-10
%I Elsevier
%R 10.1016/j.crma.2009.03.008
%G fr
%F CRMATH_2009__347_9-10_463_0
Youssef Boudabbous; Abdeljelil Salhi. Les graphes critiquement sans duo. Comptes Rendus. Mathématique, Volume 347 (2009) no. 9-10, pp. 463-466. doi : 10.1016/j.crma.2009.03.008. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2009.03.008/

[1] J.L. Beauvois, G. Lopez, Un opérateur de densification d'un graphe. Le graphe des parentés, Soumis, 2008

[2] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. (2008), in press

[3] J.F. Culus; B. Jouve Tournois sans intervalle acyclique, C. R. Acad. Sci. Paris, Ser. I, Volume 341 (2005), pp. 465-468

[4] R. Fraïssé Abritement entre relations et spécialement entre chaînes, Symposi. Math., Instituto Nazionale di Alta Matematica, Volume 5 (1970), pp. 203-251

[5] P. Ille Indecomposable graphs, Discrete Math., Volume 173 (1997), pp. 71-78

[6] J.H. Schmerl; W.T. Trotter Critically indecomposable partially ordered sets, graphs, tounaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205

Cité par Sources :

Commentaires - Politique