Les graphes critiquement sans duo

RésuméSoit G=(S,A) un graphe (orienté). Le graphe G est un tournoi si pour x,y∈S, (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,b∈I et x∈S\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 x∈S, 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. Pour citer cet article : Y. Boudabbous, A. Salhi, C. R. Acad. Sci. Paris, Ser. I 347 (2009).

Let G=(V,A) be a digraph. G is a tournament if for x,y∈V, (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,b∈I and x∈V\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 x∈V, 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. To cite this article: Y. Boudabbous, A. Salhi, C. R. Acad. Sci. Paris, Ser. I 347 (2009).