Vicinal orders of trees (Q810522)

The vicinal order of a graph \(G=(V,E)\) is the partial order on the equivalence classes of its vertices defined as follows. Let N(u) denote the neighborhood (i.e. the set of adjacent vertices) of u. Define the equivalence relation on \(V:u\approx v\) if \(N(u)\subseteq N(v)\cup \{v\}\) and \(N(v)\subseteq N(u)\cup \{u\}\) and denote the equivalence class of \(u\in V\) by [u]. The vicinal order of G is the poset \((V/\approx,\leq)\) where the ordering \(\leq\) is defined \([u]\leq [v]\) iff \(N(u)\subseteq N(v)\cup \{v\}.\) The height of the vicinal order of G is the length of the longest chain in the poset. It is shown that the height of the vicinal order of any tree with at least two internal vertices is 1. The problem arises: having a partial order, with at least 4 elements, of height 1 is it realizable as the vicinal order of some tree? The problem is solved by algorithms construting such trees in cases when the answer is positive. Failure of the approach proves nonexistence of such a tree.