Extended Lucas cubes

Abstract

A Fibonacci string of order n is a binary string of length n with no two consecutive ones. A Fibonacci string of order n which does not have a one in both the first and last postition is called a Lucas string of order n. The Lucas cube A_n is the subgraph of the hypercube Q_n induced by the set of Lucas strings. For positive integers i, n, with n > i > 1, the ith extended Lucas cube of order n, denoted by Λ_n ⁱJ, is a vertex induced subgraph of Q_n, where V(Λ_nⁱ) = V̂_nⁱ is defined recursively by the relation: V̂_nⁱ = V̂_n-1^i-1 + V̂_n-1^i-11 and the initial conditions V̂₁⁰ = {0,1}, V̂_n⁰ = V(Λ_n) for n ≥ 2. We show that with the single exception of Λ₄¹, all extended Lucas cubes λ_nⁱ with n > i > 1, are Hamiltonian and that the sequence of orders of the ith and jth Lucas cubes, t < j, are disjoint when n > i + 4.