Geodesic
Decomposition tree and indecomposable coverings
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 37-44

Voir la notice de l'article provenant de la source Library of Science

Let G = (V,A) be a directed graph. With any subset X of V is associated the directed subgraph G[X] = (X,A ∩ (X×X)) of G induced by X. A subset X of V is an interval of G provided that for a,b ∈ X and x ∈ V∖X, (a,x) ∈ A if and only if (b,x) ∈ A, and similarly for (x,a) and (x,b). For example ∅, V, and x, where x ∈ V, are intervals of G which are the trivial intervals. A directed graph is indecomposable if all its intervals are trivial. Given an integer k > 0, a directed graph G = (V,A) is called an indecomposable k-covering provided that for every subset X of V with |X| ≤ k, there exists a subset Y of V such that X ⊆ Y, G[Y] is indecomposable with |Y| ≥ 3. In this paper, the indecomposable k-covering directed graphs are characterized for any k > 0.
Keywords: interval, indecomposable, k-covering, decomposition tree 
@article{DMGT_2011_31_1_a2,
     author = {Breiner, Andrew and Deogun, Jitender and Ille, Pierre},
     title = {Decomposition tree and indecomposable coverings},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {37--44},
     publisher = {mathdoc},
     volume = {31},
     number = {1},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a2/}
}
TY  - JOUR
AU  - Breiner, Andrew
AU  - Deogun, Jitender
AU  - Ille, Pierre
TI  - Decomposition tree and indecomposable coverings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 37
EP  - 44
VL  - 31
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a2/
LA  - en
ID  - DMGT_2011_31_1_a2
ER  - 
%0 Journal Article
%A Breiner, Andrew
%A Deogun, Jitender
%A Ille, Pierre
%T Decomposition tree and indecomposable coverings
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 37-44
%V 31
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a2/
%G en
%F DMGT_2011_31_1_a2
Breiner, Andrew; Deogun, Jitender; Ille, Pierre. Decomposition tree and indecomposable coverings. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 1, pp. 37-44. http://geodesic.mathdoc.fr/item/DMGT_2011_31_1_a2/