Comptes Rendus
Logique/Combinatoire
Support critique d'un graphe indécomposable
Comptes Rendus. Mathématique, Volume 347 (2009) no. 1-2, pp. 1-4.

É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,bI et xSI, (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ù xS, 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.

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,bI and xVI, (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 xV, 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 xV 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.

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

Mohamed Yahia Sayar 1

1 Faculté des sciences de Sfax, département de mathématiques, route de la soukra km 4, BP 802, 3018 Sfax, Tunisie
@article{CRMATH_2009__347_1-2_1_0,
     author = {Mohamed Yahia Sayar},
     title = {Support critique d'un graphe ind\'ecomposable},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1--4},
     publisher = {Elsevier},
     volume = {347},
     number = {1-2},
     year = {2009},
     doi = {10.1016/j.crma.2008.10.018},
     language = {fr},
}
TY  - JOUR
AU  - Mohamed Yahia Sayar
TI  - Support critique d'un graphe indécomposable
JO  - Comptes Rendus. Mathématique
PY  - 2009
SP  - 1
EP  - 4
VL  - 347
IS  - 1-2
PB  - Elsevier
DO  - 10.1016/j.crma.2008.10.018
LA  - fr
ID  - CRMATH_2009__347_1-2_1_0
ER  - 
%0 Journal Article
%A Mohamed Yahia Sayar
%T Support critique d'un graphe indécomposable
%J Comptes Rendus. Mathématique
%D 2009
%P 1-4
%V 347
%N 1-2
%I Elsevier
%R 10.1016/j.crma.2008.10.018
%G fr
%F CRMATH_2009__347_1-2_1_0
Mohamed Yahia Sayar. Support critique d'un graphe indécomposable. Comptes Rendus. Mathématique, Volume 347 (2009) no. 1-2, pp. 1-4. doi : 10.1016/j.crma.2008.10.018. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2008.10.018/

[1] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, à paraître dans Discrete Math

[2] A. Ehrenfeucht; G. Rozenberg Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358

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

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

Cité par Sources :

Commentaires - Politique