We show three main results concerning Hamiltonicity of graphs derived from antimatroids. These results provide Gray codes for the feasible sets and basic words of antimatroids.

For antimatroid (*E*,**F**), let *J*(**F**) denote the
graph whose vertices are the sets of **F**, where two
vertices are adjacent if the corresponding sets differ
by one element. Define *J*(**F**;*k*) to be the subgraph of
*J*(**F**)^{2} induced by the sets in **F** with
exactly *k* elements. Both graphs *J*(**F**) and
*J*(**F**;*k*) are connected, and the former is bipartite.

We show that there is a Hamiltonian
cycle in *J*(**F**) x *K*_{2}.
As a consequence, the ideals of any poset **P**
may be listed in such a way that successive ideals differ
by at most two elements.
We also show that *J*(**F**;*k*) has a
Hamilton path if (*E*,**F**) is the poset antimatroid
of a series-parallel poset.

Similarly, we show that *G*(**L**) x *K*_{2} is
Hamiltonian, where *G*(**L**) is the "basic word graph"
of a language antimatroid (*E*,**L**).
This result was known previously for poset antimatroids.

**Keywords:** Antimatroid, basic word graph,
combinatorial Gray code, Hamiltonicity, join-distributive lattice.

**AMS Classification:** 05C45, 06A05, 06A06.

Comments:

- The postscript file is 230K bytes, the dvi file is 71K bytes.
- Appeared in the journal
*Order*, 10 (1993) 239-252.

Back to Frank Ruskey's publication list.