# Decomposition tree and indecomposable coverings

Andrew Breiner; Jitender Deogun; Pierre Ille

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 1, page 37-44
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAndrew Breiner, Jitender Deogun, and Pierre Ille. "Decomposition tree and indecomposable coverings." Discussiones Mathematicae Graph Theory 31.1 (2011): 37-44. <http://eudml.org/doc/270976>.

@article{AndrewBreiner2011,

abstract = {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.},

author = {Andrew Breiner, Jitender Deogun, Pierre Ille},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {interval; indecomposable; k-covering; decomposition tree; -covering},

language = {eng},

number = {1},

pages = {37-44},

title = {Decomposition tree and indecomposable coverings},

url = {http://eudml.org/doc/270976},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Andrew Breiner

AU - Jitender Deogun

AU - Pierre Ille

TI - Decomposition tree and indecomposable coverings

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 1

SP - 37

EP - 44

AB - 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.

LA - eng

KW - interval; indecomposable; k-covering; decomposition tree; -covering

UR - http://eudml.org/doc/270976

ER -

## References

top- [1] R. McConnell and F. de Montgolfier, Linear-time modular decomposition of directed graphs, Discrete Appl. Math. 145 (2005) 198-209, doi: 10.1016/j.dam.2004.02.017. Zbl1055.05123
- [2] A. Cournier and M. Habib, An efficient algorithm to recognize prime undirected graphs, in: Graph-theoretic Concepts in Computer Science, Lecture Notes in Computer Science 657, E.W. Mayr, (Editor), (Springer, Berlin, 1993) 212-224. Zbl0925.05051
- [3] A. Ehrenfeucht and G. Rozenberg, Theory of 2-structures. I. Clans, basic subclasses, and morphisms, Theoret. Comput. Sci. 70 (1990) 277-303, doi: 10.1016/0304-3975(90)90129-6. Zbl0701.05051
- [4] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25-66, doi: 10.1007/BF02020961.
- [5] M. Habib, Substitution des structures combinatoires, théorie et algorithmes, Ph.D. Thesis, Université Pierre et Marie Curie, Paris VI, 1981.
- [6] P. Ille, Indecomposable graphs, Discrete Math. 173 (1997) 71-78, doi: 10.1016/S0012-365X(96)00097-0. Zbl0882.05108
- [7] D. Kelly, Comparability graphs, in: Graphs and Orders, I. Rival, (Editor), Reidel (Drodrecht, 1985) 3-40.
- [8] F. Maffray and M. Preissmann, A translation of Tibor Gallai's paper: transitiv orientierbare Graphen, in: Perfect Graphs, J.J. Ramirez-Alfonsin and B.A. Reed, (Editors) (Wiley, New York, 2001) 25-66. Zbl0989.05050
- [9] J. Schmerl and W. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math. 113 (1993) 191-205, doi: 10.1016/0012-365X(93)90516-V. Zbl0776.06002
- [10] J. Spinrad, P₄-trees and substitution decomposition, Discrete Appl. Math. 39 (1992) 263-291, doi: 10.1016/0166-218X(92)90180-I. Zbl0758.68036

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.