PDF

Discussiones Mathematicae Graph Theory 26(3) (2006) 413-418
DOI: https://doi.org/10.7151/dmgt.1333

A NOTE ON JOINS OF ADDITIVE HEREDITARY GRAPH PROPERTIES

Ewa Drgas-Burchardt

Faculty of Mathematics, Computer Science and Econometrics
University of Zielona Góra
Prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
e-mail: E.Drgas-Burchardt@wmie.uz.zgora.pl

Abstract

Let L^a denote a set of additive hereditary graph properties. It is a known fact that a partially ordered set (L^a, ⊆ ) is a complete distributive lattice. We present results when a join of two additive hereditary graph properties in (L^a, ⊆ ) has a finite or infinite family of minimal forbidden subgraphs.

Keywords: hereditary property, lattice of additive hereditary graph properties, minimal forbidden subgraph family, join in the lattice.

2000 Mathematics Subject Classification: 05C75, 05C15, 05C35.

References

[1]	A.J. Berger, Minimal forbidden subgraphs of reducible graph properties, Discuss. Math. Graph Theory 21 (2001) 111-117, doi: 10.7151/dmgt.1136.
[2]	A.J. Berger, I. Broere, S.J.T. Moagi and P. Mihók, Meet- and join-irreducibility of additive hereditary properties of graphs, Discrete Math. 251 (2002) 11-18, doi: 10.1016/S0012-365X(01)00323-5.
[3]	M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishawa International Publication, Gulbarga, 1991) 41-68.
[4]	I. Broere, M. Frick and G.Semanišin, Maximal graphs with respect to hereditary properties, Discuss. Math. Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038.
[5]	D.L. Greenwell, R.L. Hemminger and J. Klerlein, Forbidden subgraphs, Proceedings of the 4th S-E Conf. Combinatorics, Graph Theory and Computing (Utilitas Math., Winnipeg, Man., 1973) 389-394.
[6]	J. Jakubik, On the Lattice of Additive Hereditary Properties of Finite Graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86.

Received 14 February 2006
Revised 25 September 2006