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]

Presented by: 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$ .

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

@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/

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