PDF

Discussiones Mathematicae General Algebra and Applications 22(1) (2002) 73-86
DOI: https://doi.org/10.7151/dmgaa.1048

ON THE LATTICE OF ADDITIVE HEREDITARY PROPERTIES OF FINITE GRAPHS

Ján Jakubík

 Matemathical Institute, Slovak Academy of Sciences
Gresákova 6, 040-01 Kosice, Slovakia
e-mail: kstefan@saske.sk

Abstract

In this paper it is proved that the lattice of additive hereditary properties of finite graphs is completely distributive and that it does not satisfy the Jordan-Dedekind condition for infinite chains.

 Keywords: Lattice, complete distributivity, finite graph, additive hereditary property, generalized Jordan-Dedekind condition.

 2000 AMS Mathematics Subject Classifications: 06D10, 05C99.

 References

[1] G. Birkhoff, Lattice Theory, (the 3-rd ed.), Amer. Math. Soc., Providence, RI, 1967.

[2] M. Borowiecki, I. Broere, M. Frick, P. Mihók, and G. Semanisin, A survey of hereditary properties of graphs, Discussiones Math.- Graph Theory 17 (1997), 5-50.

[3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, p. 41-68 in: ``Advances in Graph Theory'', Vishwa International Publications, Gulbarga 1991.

[4] G. Grätzer and E. T. Schmidt, On the Jordan-Dedekind chain condition, Acta Sci. Math. 18 (1957), 52-56.

[5] J. Jakubík, On the Jordan-Dedekind chain condition, Acta Sci. Math. 16 (1955), 266-269.

[6] J. Jakubík, A remark on the Jordan-Dedekind chain condition in Boolean algebras (Slovak), Casopis Pest. Mat. 82 (1957), 44-46.

[7] J. Jakubík, On chains in Boolean algebras (Slovak), Mat. Fyz. Casopis SAV 8 (1958), 193-202.

[8] J. Jakubí k, Die Jordan-Dedekindsche Bedingung im direkten Produkt von geordneten Mengen, Acta Sci. Math. 24 (1963), 20-23.

[9] P. Mihók, On graphs critical with respect to generalized independence numbers, Colloq. Math. Soc. J. Bolyai 52 (1987), 417-421.

[10] G.N. Raney, Completely distributive complete lattices, Proc. Amer. Math. Soc. 3 (1952), 677-680.

[11] G.N. Raney, A subdirect-union representation for completely distributive lattices, Proc. Amer. Math. Soc. 4 (1952), 518-522.

[12] G.N. Raney, Tight Galois connection and complete distributivity, Trans. Amer. Math. Soc. 97 (1960), 418-426.

[13] R. Sikorski, Boolean Algebras (the second edition), Springer-Verlag, Berlin 1964.

[14] G. Szász, Generalization of a theorem of Birkhoff concerning maximal chains of a certain type of lattices, Acta Sci. Math. 16 (1955), 89-91.

Received 29 February 2002