ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 31(1) (2011) 37-44
DOI: 10.7151/dmgt.1528


Andrew Breiner

Department of Mathematics and Computer Science
Nebraska Wesleyan University
5000 St. Paul Avenue, Lincoln, NE 68504, USA

Jitender Deogun

Department of Computer Science and Engineering
University of Nebraska - Lincoln
Lincoln, NE 68588-0115, USA

Pierre Ille

C.N.R.S. - UMR 6206
Institut de Mathématiques de Luminy
163, Avenue de Luminy - Case 907
13288 Marseille Cedex 9, France


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.

2010 Mathematics Subject Classification: 05C20, 05C75.


[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.
[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.
[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.
[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.
[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.
[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.
[10] J. Spinrad, P4-trees and substitution decomposition, Discrete Appl. Math. 39 (1992) 263-291, doi: 10.1016/0166-218X(92)90180-I.

Received 11 June 2008
Revised 29 March 2010
Accepted 6 April 2010