- Tytuł:
- Decomposition tree and indecomposable coverings
- Autorzy:
-
Breiner, Andrew
Deogun, Jitender
Ille, Pierre - Powiązania:
- https://bibliotekanauki.pl/articles/744120.pdf
- Data publikacji:
- 2011
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
interval
indecomposable
k-covering
decomposition tree - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 37-44
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł