[Critical support of an indecomposable graph]
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 .
É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 .
Accepted:
Published online:
Mohamed Yahia Sayar 1
@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}, }
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] 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
Cited by Sources:
Comments - Policy