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

[BIBTex] [PDF] [PS]

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