Decomposition tree and indecomposable coverings

Andrew Breiner, Jitender Deogun, Pierre Ille

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)37-44
Number of pages8
JournalDiscussiones Mathematicae - Graph Theory
Issue number1
StatePublished - 2011
Externally publishedYes


  • decomposition tree
  • indecomposable
  • interval
  • k-covering

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Decomposition tree and indecomposable coverings'. Together they form a unique fingerprint.

Cite this