Observability of the 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 t he first and last postition is called a Lucas string of order n . The Lucas cube An is the subgraph of the hypercube Qn induced by the set of Lucas strings. For positive integers in , with n > i 2'. 1, th e ith extended Lucas cube of order n, denoted by A~ , is a vert.ex induced subgraph of Qn, where V(A~) = \/~ is defined recursively by the relation : and the initial conditions Vi° = {O , I}, V,; = V(An) for n 2'. 2. We consider the number of colours required for a strong edge colouring of A~ and prove that for n 2'. 3, obs(A~) = n + 1 when i = 1 and i = 2, and obtain bounds on obs(A~) for n > i 2'. 3.