Étant donné un graphe orienté , à chaque partie X de S est associé le sous-graphe de G induit par X. Une partie I de S est un intervalle de G si pour tous et , si et seulement si , et si et seulement si . Par exemple, ∅, S et , où , 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 , le support de G est l'ensemble des sommets x de G tels que est indécomposable. Son support critique est l'ensemble des éléments x de tels que . Pour tout graphe orienté , nous montrons que si G est indécomposable et si , alors .
Given a digraph , with each subset X of V is associated the subgraph of G induced by X. A subset I of V is an interval of G provided that for any and , if and only if , and if and only if . For example, ∅, V and , where , are intervals of G called trivial intervals. A digraph is indecomposable if all its intervals are trivial. Given an indecomposable digraph , the support of G is the set of vertices such that is indecomposable. Its critical support is the set of the elements x of such that . For every digraph , we prove that if G is indecomposable and if , then .
Accepté le :
Publié le :
@article{CRMATH_2009__347_1-2_1_0, author = {Sayar, Mohamed Yahia}, 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}, url = {http://archive.numdam.org/articles/10.1016/j.crma.2008.10.018/} }
TY - JOUR AU - Sayar, Mohamed Yahia 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 UR - http://archive.numdam.org/articles/10.1016/j.crma.2008.10.018/ DO - 10.1016/j.crma.2008.10.018 LA - fr ID - CRMATH_2009__347_1-2_1_0 ER -
Sayar, Mohamed Yahia. Support critique d'un graphe indécomposable. Comptes Rendus. Mathématique, Tome 347 (2009) no. 1-2, pp. 1-4. doi : 10.1016/j.crma.2008.10.018. http://archive.numdam.org/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] Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358
[3] Indecomposable graphs, Discrete Math., Volume 173 (1997), pp. 71-78
[4] Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205
Cité par Sources :