6533b824fe1ef96bd128013f

RESEARCH PRODUCT

Minimal change list for Lucas strings and some graph theoretic consequences

Vincent VajnovszkiJean-luc Baril

subject

Fibonacci numberGeneral Computer ScienceLucas sequenceCube (algebra)Fibonacci and Lucas stringHamiltonian pathTheoretical Computer ScienceCombinatoricsGray codeSet (abstract data type)symbols.namesakesymbolsHamiltonian pathOrder (group theory)Minimal change listSuffixGray codeLucas cubeComputer Science(all)Mathematics

description

AbstractWe give a minimal change list for the set of order p length-n Lucas strings, i.e., the set of length-n binary strings with no p consecutive 1's nor a 1ℓ prefix and a 1m suffix with ℓ+m⩾p. The construction of this list proves also that the order p n-dimensional Lucas cube has a Hamiltonian path if and only if n is not a multiple of p+1, and its second power always has a Hamiltonian path.

yearjournalcountryeditionlanguage
2005-11-01Theoretical Computer Science
10.1016/j.tcs.2005.08.020http://dx.doi.org/10.1016/j.tcs.2005.08.020