Graphs orientable as distributive lattices

Duffus, Dwight; Rival, Ivan

doi:10.1090/S0002-9939-1983-0695239-4

Graphs orientable as distributive lattices
HTML articles powered by AMS MathViewer

by Dwight Duffus and Ivan Rival

Proc. Amer. Math. Soc. 88 (1983), 197-200

DOI: https://doi.org/10.1090/S0002-9939-1983-0695239-4

PDF | Request permission

Abstract:

There are two types of graphs commonly associated with finite (partially) ordered sets: the comparability graph and the covering graph. While the first type has been characterized, only partial descriptions of the second are known. We prove that the covering graphs of distributive lattices are precisely those graphs which are retracts of hypercubes.

References

-orientable graphs

Laurence R. Alvarez, Undirected graphs realizable as graphs of modular lattices, Canadian J. Math. 17 (1965), 923–932. MR 182573, DOI 10.4153/CJM-1965-088-1
Dwight Duffus and Ivan Rival, Path length in the covering graph of a lattice, Discrete Math. 19 (1977), no. 2, 139–158. MR 543829, DOI 10.1016/0012-365X(77)90029-2
Alain Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienter les arětes de manière à obtenir le graphe d’une relation d’ordre, C. R. Acad. Sci. Paris 254 (1962), 1370–1371 (French). MR 172275
P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canadian J. Math. 16 (1964), 539–548. MR 175811, DOI 10.4153/CJM-1964-055-5
Ján Jakubík, On lattices whose graphs are isomorphic, Čehoslovack. Mat. Ž. 4(79) (1954), 131–141 (Russian, with English summary). MR 0065530
J. Jakubík, Modular lattices of locally finite length, Acta Sci. Math. (Szeged) 37 (1975), 79–82. MR 382094
K. M. Mosesjan, Basable and strongly basable graphs, Akad. Nauk Armjan. SSR Dokl. 55 (1972), 83–86 (Russian, with Armenian summary). MR 327562
Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR 0150753
Ivan Rival, Maximal sublattices of finite distributive lattices. II, Proc. Amer. Math. Soc. 44 (1974), 263–268. MR 360393, DOI 10.1090/S0002-9939-1974-0360393-5