DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 229-236
DOI: 10.7151/dmgt.1097

ON THE COMPLETENESS OF DECOMPOSABLE PROPERTIES OF GRAPHS

Mariusz Hałuszczak

Institute of Mathematics
Technical University of Zielona Góra
Podgórna 50, 65-246 Zielona Góra, Poland
e-mail: M.Hałuszczak@im.uz.zgora.pl

Pavol Vateha

Department of Geometry and Algebra
Faculty of Science, P.J. Safárik University
Jesenná 5, 041 54 Košice, Slovak Republic
e-mail: vateha@duro.upjs.sk

Abstract

Let P1, P2 be additive hereditary properties of graphs. A (P1, P2)-decomposition of a graph G is a partition of E(G) into sets E1, E2 such that induced subgraph G[Ei] has the property Pi, i = 1,2. Let us define a property P1P2 by {G: G has a (P1,P2)-decomposition}.

A property D is said to be decomposable if there exists nontrivial additive hereditary properties P1, P2 such that D = P1P2. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness 2.

Keywords: decomposition, hereditary property, completeness.

1991 Mathematics Subject Classification: 05C55, 05C70.

References

[1] L.W. Beineke, Decompositions of complete graphs into forests, Magyar Tud. Akad. Mat. Kutato Int. Kozl. 9 (1964) 589-594.
[2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
[3] M. Borowiecki and M. Hałuszczak, Decomposition of some classes of graphs, (manuscript).
[4] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68.
[5] S.A. Burr, J.A. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973) 217-220
[6] G. Chartrand and L. Lesnak, Graphs and Digraphs (Wadsworth & Brooks/Cole, Monterey, California, 1986).
[7] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2.
[8] P. Mihók Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki, Z. Skupień, eds., Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.
[9] P. Mihók and G. Semanišin, Generalized Ramsey Theory and Decomposable Properties of Graphs, (manuscript).
[10] L. Volkmann, Fundamente der Graphentheorie (Springer, Wien, New York, 1996), doi: 10.1007/978-3-7091-9449-2.

Received 12 February 1999
Revised 20 October 1999