Graphs orientable as distributive lattices

Authors:
Dwight Duffus and Ivan Rival

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

MSC:
Primary 05C75; Secondary 06D99

MathSciNet review:
695239

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**M. Aigner and G. Prins,*-orientable graphs*(preprint 1980).**[2]**Laurence R. Alvarez,*Undirected graphs realizable as graphs of modular lattices*, Canad. J. Math.**17**(1965), 923–932. MR**0182573****[3]**Dwight Duffus and Ivan Rival,*Path length in the covering graph of a lattice*, Discrete Math.**19**(1977), no. 2, 139–158. MR**0543829****[4]**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**0172275****[5]**P. C. Gilmore and A. J. Hoffman,*A characterization of comparability graphs and of interval graphs*, Canad. J. Math.**16**(1964), 539–548. MR**0175811****[6]**Ján Jakubík,*On lattices whose graphs are isomorphic*, Čehoslovack. Mat. Ž.**4(79)**(1954), 131–141 (Russian, with English summary). MR**0065530****[7]**J. Jakubík,*Modular lattices of locally finite length*, Acta Sci. Math. (Szeged)**37**(1975), 79–82. MR**0382094****[8]**K. M. Mosesjan,*Basable and strongly basable graphs*, Akad. Nauk Armjan. SSR Dokl.**55**(1972), 83–86 (Russian, with Armenian summary). MR**0327562****[9]**Oystein Ore,*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR**0150753****[10]**Ivan Rival,*Maximal sublattices of finite distributive lattices. II*, Proc. Amer. Math. Soc.**44**(1974), 263–268. MR**0360393**, 10.1090/S0002-9939-1974-0360393-5

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
05C75,
06D99

Retrieve articles in all journals with MSC: 05C75, 06D99

Additional Information

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

Article copyright:
© Copyright 1983
American Mathematical Society