ISSN:
1572-9273
Keywords:
05C45
;
06A05
;
06A06
;
Antimatroid
;
basic word graph
;
combinatorial Gray code
;
Hamiltonicity
;
join-distributive lattice
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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, $$\mathcal{F}$$ ), letJ( $$\mathcal{F}$$ ) denote the graph whose vertices are the sets of $$\mathcal{F}$$ , where two vertices are adjacent if the corresponding sets differ by one element. DefineJ( $$\mathcal{F}$$ ;k) to be the subgraph ofJ( $$\mathcal{F}$$ )2 induced by the sets in $$\mathcal{F}$$ with exactlyk elements. Both graphsJ( $$\mathcal{F}$$ ) andJ( $$\mathcal{F}$$ ;k) are connected, and the former is bipartite. We show that there is a Hamiltonian cycle inJ( $$\mathcal{F}$$ )×K 2. As a consequence, the ideals of any poset % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf% gDOfdaryqr1ngBPrginfgDObYtUvgaiuaacqWFpepuaaa!414C!\[\mathcal{P}\] may be listed in such a way that successive ideals differ by at most two elements. We also show thatJ( $$\mathcal{F}$$ ;k) has a Hamilton path if (E, $$\mathcal{F}$$ ) is the poset antimatroid of a series-parallel poset. Similarly, we show thatG( $$\mathcal{L}$$ )×K 2 is Hamiltonian, whereG( $$\mathcal{L}$$ ) is the “basic word graph” of a language antimatroid (E, $$\mathcal{L}$$ ). This result was known previously for poset antimatroids.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01110545
Permalink
