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

Abstract

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

How to cite

top

Andrew 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. [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. [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. [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. [4] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25-66, doi: 10.1007/BF02020961. 
  5. [5] M. Habib, Substitution des structures combinatoires, théorie et algorithmes, Ph.D. Thesis, Université Pierre et Marie Curie, Paris VI, 1981. 
  6. [6] P. Ille, Indecomposable graphs, Discrete Math. 173 (1997) 71-78, doi: 10.1016/S0012-365X(96)00097-0. Zbl0882.05108
  7. [7] D. Kelly, Comparability graphs, in: Graphs and Orders, I. Rival, (Editor), Reidel (Drodrecht, 1985) 3-40. 
  8. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.