E. ARAGNO and N. ZAGAGLIA SALVI

Widened Fibonacci cubes

Pages: 25-35
Received: 1 February 2000   
Mathematics Subject Classification (2000): 05C15 - 05C45

Work partially supported by M.U.R.S.T.

Abstract: We introduce the widened Fibonacci cube, a graph, embedded in the hypercube, which contains the Fibonacci cube as induced subgraph and provides many of the properties of the Fibonacci cube with in addition the hamiltonicity for every number of vertices. The values of the diameter, radius, center and independence number are determined, together with its observability, which is the minimum number of colors assignable to the edges so that the coloring is proper and the vertices are distinguished by their color sets. Finally we prove it is isomorphic to the Hasse diagram of a particular semilattice.