Support critique d'un graphe indécomposable

RésuméÉtant donné un graphe orienté G=(S,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. Par exemple, ∅, S et {x}, où x∈S, sont des intervalles de G appelés intervalles triviaux. Un graphe orienté est indécomposable si tous ses intervalles sont triviaux. Étant donné un graphe orienté et indécomposable G=(S,A), le support de G est l'ensemble σ(G) des sommets x de G tels que G[S∖{x}] est indécomposable. Son support critique est l'ensemble σC(G) des éléments x de σ(G) tels que σ(G[S∖{x}])=∅. Pour tout graphe orienté G=(S,A), nous montrons que si G est indécomposable et si |S|⩾7, alors |σC(G)|⩽2. Pour citer cet article : M.Y. Sayar, C. R. Acad. Sci. Paris, Ser. I 347 (2009).

Given a digraph G=(V,A), with each subset X of V is associated the subgraph G[X]=(X,A∩(X×X)) of G induced by 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. For example, ∅, V and {x}, where x∈V, are intervals of G called trivial intervals. A digraph is indecomposable if all its intervals are trivial. Given an indecomposable digraph G=(V,A), the support of G is the set σ(G) of vertices x∈V such that G[V∖{x}] is indecomposable. Its critical support is the set σC(G) of the elements x of σ(G) such that σ(G[V∖{x}])=∅. For every digraph G=(V,A), we prove that if G is indecomposable and if |V|⩾7, then |σC(G)|⩽2. To cite this article: M.Y. Sayar, C. R. Acad. Sci. Paris, Ser. I 347 (2009).