Les graphes critiquement sans duo

Youssef Boudabbous; Abdeljelil Salhi

doi:10.1016/j.crma.2009.03.008

Logique/Combinatoire

Les graphes critiquement sans duo

Présenté par : Jean-Yves Girard

Youssef Boudabbous ¹ ; Abdeljelil Salhi ²

¹ Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie
² Faculté des sciences de Gafsa, 2112 Gafsa, Tunisie

Comptes Rendus. Mathématique, Volume 347 (2009) no. 9-10, pp. 463-466.

Résumé
Abstract

Soit $G = (S, A)$ un graphe (orienté). Le graphe G est un tournoi si pour $x, y \in S$ , $(x, y) \in A$ si et seulement si $(y, x) \notin 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$ . Un duo de G est un intervalle de G à deux éléments. Le graphe G est critiquement sans duo s'il est sans duo et si pour tout $x \in S$ , le sous-graphe $G [S \ {x}]$ admet au moins un duo. Suite à l'étude des tournois acycliques, faite par J.F. Culus et B. Jouve en 2005, nous donnons, dans cette Note, une description morphologique complète des graphes critiquement sans duo.

Let $G = (V, A)$ be a digraph. G is a tournament if for $x, y \in V$ , $(x, y) \in A$ if and only if $(y, x) \notin A$ . The induced subgraph of G by a subset X of V is denoted by $G [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$ . An interval of G on 2 elements is called duo of G. G is called critically without duo if it is without duo and for all $x \in V$ , the subgraph $G [V \ {x}]$ has at least one duo. Following the study of acyclic tournaments made by J.F. Culus and B. Jouve in 2005, we give, in this Note, a complete morphologic description of critically without duo graphs.

Reçu le : 2009-02-13
Accepté le : 2009-02-17
Publié le : 2009-04-02

DOI : 10.1016/j.crma.2009.03.008

Affiliations des auteurs :

Youssef Boudabbous ¹ ; Abdeljelil Salhi ²

¹ Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie
² Faculté des sciences de Gafsa, 2112 Gafsa, Tunisie

@article{CRMATH_2009__347_9-10_463_0,
     author = {Youssef Boudabbous and Abdeljelil Salhi},
     title = {Les graphes critiquement sans duo},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {463--466},
     publisher = {Elsevier},
     volume = {347},
     number = {9-10},
     year = {2009},
     doi = {10.1016/j.crma.2009.03.008},
     language = {fr},
}

TY  - JOUR
AU  - Youssef Boudabbous
AU  - Abdeljelil Salhi
TI  - Les graphes critiquement sans duo
JO  - Comptes Rendus. Mathématique
PY  - 2009
SP  - 463
EP  - 466
VL  - 347
IS  - 9-10
PB  - Elsevier
DO  - 10.1016/j.crma.2009.03.008
LA  - fr
ID  - CRMATH_2009__347_9-10_463_0
ER  -

%0 Journal Article
%A Youssef Boudabbous
%A Abdeljelil Salhi
%T Les graphes critiquement sans duo
%J Comptes Rendus. Mathématique
%D 2009
%P 463-466
%V 347
%N 9-10
%I Elsevier
%R 10.1016/j.crma.2009.03.008
%G fr
%F CRMATH_2009__347_9-10_463_0

Youssef Boudabbous; Abdeljelil Salhi. Les graphes critiquement sans duo. Comptes Rendus. Mathématique, Volume 347 (2009) no. 9-10, pp. 463-466. doi : 10.1016/j.crma.2009.03.008. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2009.03.008/

Bibliographie
Cité par

[1] J.L. Beauvois, G. Lopez, Un opérateur de densification d'un graphe. Le graphe des parentés, Soumis, 2008

[2] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. (2008), in press

[3] J.F. Culus; B. Jouve Tournois sans intervalle acyclique, C. R. Acad. Sci. Paris, Ser. I, Volume 341 (2005), pp. 465-468

[4] R. Fraïssé Abritement entre relations et spécialement entre chaînes, Symposi. Math., Instituto Nazionale di Alta Matematica, Volume 5 (1970), pp. 203-251

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

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

Cité par Sources :

Commentaires - Politique