Discrete ordered sets whose covering graphs are median
HTML articles powered by AMS MathViewer
- by Hans-J. Bandelt PDF
- Proc. Amer. Math. Soc. 91 (1984), 6-8 Request permission
Abstract:
As is well known the covering graph (= Hasse diagram) of any median semilattice is a median graph, and every median graph is the covering graph of some median semilattice. The purpose of this note is to prove that an ordered set is a median semilattice whenever (i) no interval contains an infinite chain, (ii) each pair of elements is bounded below, and (iii) the covering graph is median.References
- 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
- S. P. Avann, Metric ternary distributive semi-lattices, Proc. Amer. Math. Soc. 12 (1961), 407–414. MR 125807, DOI 10.1090/S0002-9939-1961-0125807-5
- Hans-J. Bandelt and Jarmila Hedlíková, Median algebras, Discrete Math. 45 (1983), no. 1, 1–30. MR 700848, DOI 10.1016/0012-365X(83)90173-5
- Dwight Duffus and Ivan Rival, Graphs orientable as distributive lattices, Proc. Amer. Math. Soc. 88 (1983), no. 2, 197–200. MR 695239, DOI 10.1090/S0002-9939-1983-0695239-4
- H. M. Mulder and A. Schrijver, Median graphs and Helly hypergraphs, Discrete Math. 25 (1979), no. 1, 41–50. MR 522746, DOI 10.1016/0012-365X(79)90151-1
- Marlow Sholander, Medians, lattices, and trees, Proc. Amer. Math. Soc. 5 (1954), 808–812. MR 64750, DOI 10.1090/S0002-9939-1954-0064750-3
Additional Information
- © Copyright 1984 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 91 (1984), 6-8
- MSC: Primary 06A10; Secondary 05C75, 06A12
- DOI: https://doi.org/10.1090/S0002-9939-1984-0735552-6
- MathSciNet review: 735552