Discussiones
Mathematicae Graph Theory 18(2) (1998) 183-195
DOI: https://doi.org/10.7151/dmgt.1074
ON HEREDITARY PROPERTIES OF COMPOSITION GRAPHS
Vadim E. Levit and Eugen Mandrescu
Department of Computer Systems
Center for Technological Education
Affiliated with Tel-Aviv University
52 Golomb St., P.O. Box 305
Holon 58102, Israel
e-mail: levitv@barley.cteh.ac.il
eugen_m@barley.cteh.ac.il
Abstract
The composition graph of a family of n+1 disjoint graphs {Hi:0 ≤ i ≤ n} is the graph H obtained by substituting the n vertices of H0 respectively by the graphs H1,H2,...,Hn. 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 {Hi: 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., P4-free graphs), is also a co-graph, whereas for θ1-perfect graphs (i.e., P4-free and C4-free graphs) and for threshold graphs (i.e., P4-free, C4-free and 2K2-free graphs), the corresponding factors {Hi:0 ≤ i ≤ n} have to be equipped with some special structure.
Keywords: composition graph, co-graphs, θ1-perfect graphs, threshold graphs.
1991 Mathematics Subject Classification: 05C38, 05C751.
References
| [1] | B. Bollobás, Extremal graph theory (Academic Press, London, 1978). |
| [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. |
| [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] | 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. |
| [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. |
| [6] | V. Chvátal and P.L. Hammer, Set-packing and threshold graphs, Res. Report CORR 73-21, University Waterloo, 1973. |
| [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. |
| [8] | M.C. Golumbic, Trivially perfect graphs, Discrete Math. 24 (1978) 105-107, doi: 10.1016/0012-365X(78)90178-4. |
| [9] | M.C. Golumbic, Algorithmic graph theory and perfect graphs (Academic Press, London, 1980). |
| [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. |
| [11] | N.V.R. Mahadev and U.N. Peled, Threshold graphs and related topics (North-Holland, Amsterdam, 1995). |
| [12] | E. Mandrescu, Triangulated graph products, Anal. Univ. Galatzi (1991) 37-44. |
| [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. |
| [14] | U.N. Peled, Matroidal graphs, Discrete Math. 20 (1977) 263-286. |
| [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. |
| [16] | G. Ravindra and K.R. Parthasarathy, Perfect Product Graphs, Discrete Math. 20 (1977) 177-186, doi: 10.1016/0012-365X(77)90056-5. |
| [17] | G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959) 693-698, doi: 10.1215/S0012-7094-59-02667-5. |
Received 21 October 1997
Revised 4 May 1998
Close