Support critique d'un graphe indécomposable

Mohamed Yahia Sayar

doi:10.1016/j.crma.2008.10.018

Logique/Combinatoire

Support critique d'un graphe indécomposable
[Critical support of an indecomposable graph]

Jean-Yves Girard

Mohamed Yahia Sayar ¹

¹Faculté des sciences de Sfax, département de mathématiques, route de la soukra km 4, BP 802, 3018 Sfax, Tunisie

Comptes Rendus. Mathématique, Volume 347 (2009) no. 1-2, pp. 1-4

Résumé (Original language)
Abstract

Étant donné un graphe orienté $G = (S, A)$ , à chaque partie X de S est associé le sous-graphe $G [X] = (X, (X \times X) \cap A)$ de G induit par X. Une partie I de S est un intervalle de G si pour tous $a, b \in I$ et $x \in S ∖ I$ , $(a, x) \in A$ si et seulement si $(b, x) \in A$ , et $(x, a) \in A$ si et seulement si $(x, b) \in A$ . Par exemple, ∅, S et ${x}$ , où $x \in 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}]) = \emptyset$ . 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 \cap (X \times X))$ of G induced by X. A subset I of V is an interval of G provided that for any $a, b \in I$ and $x \in V ∖ I$ , $(a, x) \in A$ if and only if $(b, x) \in A$ , and $(x, a) \in A$ if and only if $(x, b) \in A$ . For example, ∅, V and ${x}$ , where $x \in 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 \in 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}]) = \emptyset$ . For every digraph $G = (V, A)$ , we prove that if G is indecomposable and if $| V | ⩾ 7$ , then $| σ_{C} (G) | ⩽ 2$ .

Article information
Cite this article

Received: 2008-10-09
Accepted: 2008-10-27
Published online: 2008-11-26

DOI: 10.1016/j.crma.2008.10.018

Author's affiliations:

Mohamed Yahia Sayar ¹

¹ Faculté des sciences de Sfax, département de mathématiques, route de la soukra km 4, BP 802, 3018 Sfax, Tunisie

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

@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},
     year = {2009},
     publisher = {Elsevier},
     volume = {347},
     number = {1-2},
     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

References
Cited by

[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

Cited by Sources:

Comments - Policy