Graphs and finite distributive partial lattices
Juhani Nieminen · Tsukuba Journal of Mathematics · 1987
The Hasse diagram graph of a finite distributive partial lattice is characterized by means of prime convexes.Median graphs contitute a well known and widely studied class of graphs; see for example the papers [1] and [2] and the references therein.They consti- tute a subclass of the Hasse diagram graphs of distributive partial lattices.In this paper we give a characterization for the Hasse diagram graphs $G$ of finite distributive partial lattices by means of prime convexes of $G$ .This characterization generalizes that of Mulder and Schrijver for median graphs reprinted in [1, Theorem 2.2].A meetsemilattice $S$ is a partial lattice if for any two elements $a,$ $b$ having an upper bound in $S$ also the element $a\vee b$ belongs to $S$ .Clearly every finite meetsemilattice is a partial lattice.A partial lattice $S$ is distributive if its every subset ( $k$ ] $=\{s|s\leq k\}$ is a distributive lattice.A finite distributive partial lattice $S$ can be embedded in the distributive lattice $I(S)$ of ideals of $S$ , where the join of two ideals $I$ and $J$ is $I\vee J=$ { $s|\leq i\vee j,$ $i\in l$ and $j\in J$ }.By using this lattice we see that one shortest path joining two points $a$ and $b$ of the Hasse diagram graph $S$ contains the point $a\wedge b$ , and if $a>b$ , then every point $c,$ $a\geq c\geq b$ , is on some shortest $a-b$ path.The graphs $G=(V, X)$ considered here are finite, connected and undirected without loops and multiple lines.The points of $G$ constitute theset $V$ and itsof any shortest $a-b$ path (of any $a-b$ geodesic) for every two points $a,$ $b\in A$ .The intersection of two convexes is also a convex and thus the least convex contai- ning a given pointsetThis set is briefly denoted by $\langle B\rangle$ .A convex $A eq V$ is called prime if the set $V\backslash A$ is also a convex.The sets $\phi$ and $V$ are trivial prime convexes.A graph $G$ has the prime convex intersection property (is a primeconvex intersection graph) if its every