The observability of the Fibonacci and the Lucas cubes Original Research Article

The Fibonacci cube Γn is the graph whose vertices are binary strings of length n without two consecutive 1ʹs and two vertices are adjacent when their Hamming distance is exactly 1. If the binary strings do not contain two consecutive 1ʹs nor a 1 in the first and in the last position, we obtain the Lucas cube Ln. We prove that the observability of Γn and Ln is n, where the observability of a graph G is the minimum number of colors to be assigned to the edges of G so that the coloring is proper and the vertices are distinguished by their color sets.