On hereditary properties of composition graphs

Vadim E. Levit; Eugen Mandrescu

Discussiones Mathematicae Graph Theory (1998)

  • Volume: 18, Issue: 2, page 183-195
  • ISSN: 2083-5892

Abstract

top
The composition graph of a family of n+1 disjoint graphs H i : 0 ≤ i ≤ n is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors H i : 0 ≤ i ≤ n have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978), and the composition graph of a family of comparability graphs is a comparability graph as well (M.C. Golumbic, 1980). In this paper we show that the composition graph of a family of co-graphs (i.e., P₄-free graphs), is also a co-graph, whereas for θ₁-perfect graphs (i.e., P₄-free and C₄-free graphs) and for threshold graphs (i.e., P₄-free, C₄-free and 2K₂-free graphs), the corresponding factors H i : 0 ≤ i ≤ n have to be equipped with some special structure.

How to cite

top

Vadim E. Levit, and Eugen Mandrescu. "On hereditary properties of composition graphs." Discussiones Mathematicae Graph Theory 18.2 (1998): 183-195. <http://eudml.org/doc/270387>.

@article{VadimE1998,
abstract = {The composition graph of a family of n+1 disjoint graphs $\{H_i:0 ≤ i ≤ n\}$ is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors $\{H_i: 0 ≤ i ≤ n\}$ have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978), and the composition graph of a family of comparability graphs is a comparability graph as well (M.C. Golumbic, 1980). In this paper we show that the composition graph of a family of co-graphs (i.e., P₄-free graphs), is also a co-graph, whereas for θ₁-perfect graphs (i.e., P₄-free and C₄-free graphs) and for threshold graphs (i.e., P₄-free, C₄-free and 2K₂-free graphs), the corresponding factors $\{H_i:0 ≤ i ≤ n\}$ have to be equipped with some special structure.},
author = {Vadim E. Levit, Eugen Mandrescu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {composition graph; co-graphs; θ₁-perfect graphs; threshold graphs; composition; perfectness; comparability; permutation graph; factor graphs; composite graph},
language = {eng},
number = {2},
pages = {183-195},
title = {On hereditary properties of composition graphs},
url = {http://eudml.org/doc/270387},
volume = {18},
year = {1998},
}

TY - JOUR
AU - Vadim E. Levit
AU - Eugen Mandrescu
TI - On hereditary properties of composition graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1998
VL - 18
IS - 2
SP - 183
EP - 195
AB - The composition graph of a family of n+1 disjoint graphs ${H_i:0 ≤ i ≤ n}$ is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors ${H_i: 0 ≤ i ≤ n}$ have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978), and the composition graph of a family of comparability graphs is a comparability graph as well (M.C. Golumbic, 1980). In this paper we show that the composition graph of a family of co-graphs (i.e., P₄-free graphs), is also a co-graph, whereas for θ₁-perfect graphs (i.e., P₄-free and C₄-free graphs) and for threshold graphs (i.e., P₄-free, C₄-free and 2K₂-free graphs), the corresponding factors ${H_i:0 ≤ i ≤ n}$ have to be equipped with some special structure.
LA - eng
KW - composition graph; co-graphs; θ₁-perfect graphs; threshold graphs; composition; perfectness; comparability; permutation graph; factor graphs; composite graph
UR - http://eudml.org/doc/270387
ER -

References

top
  1. [1] B. Bollobás, Extremal graph theory (Academic Press, London, 1978). Zbl0419.05031
  2. [2] B. Bollobás and A.G. Thomason, Hereditary and monotone properties of graphs, in: R.L. Graham and J. Nešetřil, eds., The Mathematics of Paul Erdős, II, Algorithms and Combinatorics 14 (Springer-Verlag, 1997) 70-78. Zbl0866.05030
  3. [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli ed., Advances in Graph Theory (Vishwa Intern. Publication, Gulbarga,1991) 41-68. 
  4. [4] M. Borowiecki, I. Broere, M. Frick, P. Mihók, G. Semanišin, A Survey of Hereditary Properties of Graphs, Discussiones Mathematicae Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
  5. [5] P. Borowiecki and J. Ivančo, P-bipartitions of minor hereditary properties, Discussiones Mathematicae Graph Theory 17 (1997) 89-93, doi: 10.7151/dmgt.1041. Zbl0914.05057
  6. [6] V. Chvátal and P.L. Hammer, Set-packing and threshold graphs, Res. Report CORR 73-21, University Waterloo, 1973. 
  7. [7] S. Foldes and P.L. Hammer, Split graphs, in: F. Hoffman et al., eds., Proc. 8th Conf. on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, Louisiana, 1977) 311-315. Zbl0407.05071
  8. [8] M.C. Golumbic, Trivially perfect graphs, Discrete Math. 24 (1978) 105-107, doi: 10.1016/0012-365X(78)90178-4. 
  9. [9] M.C. Golumbic, Algorithmic graph theory and perfect graphs (Academic Press, London, 1980). 
  10. [10] J.L. Jolivet, Sur le joint d' une famille de graphes, Discrete Math. 5 (1973) 145-158, doi: 10.1016/0012-365X(73)90106-4. Zbl0256.05124
  11. [11] N.V.R. Mahadev and U.N. Peled, Threshold graphs and related topics (North-Holland, Amsterdam, 1995). Zbl0852.05001
  12. [12] E. Mandrescu, Triangulated graph products, Anal. Univ. Galatzi (1991) 37-44. 
  13. [13] K.R. Parthasarathy, S.A. Choudum and G. Ravindra, Line-clique cover number of a graph, Proc. Indian Nat. Sci. Acad., Part A 41 (3) (1975) 281-293. Zbl0335.05127
  14. [14] U.N. Peled, Matroidal graphs, Discrete Math. 20 (1977) 263-286. 
  15. [15] A. Pnueli, A. Lempel and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math. 23 (1971) 160-175, doi: 10.4153/CJM-1971-016-5. Zbl0204.24604
  16. [16] G. Ravindra and K.R. Parthasarathy, Perfect Product Graphs, Discrete Math. 20 (1977) 177-186, doi: 10.1016/0012-365X(77)90056-5. Zbl0371.05028
  17. [17] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-698, doi: 10.1215/S0012-7094-59-02667-5. Zbl0095.37802

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.