Publikationsdatum:
2013-10-03
Beschreibung:
Fibonacci strings are binary strings that contain no two consecutive 1s. The Fibonacci cube Γ h is the subgraph of the h -cube induced by the Fibonacci strings. These graphs are applicable as interconnection networks and in theoretical chemistry, and lead to the Fibonacci dimension of a graph. We derive a new characterization of Fibonacci cubes. The characterization is the basis for an algorithm which recognizes these graphs in linear time. Moreover, a graph which was recognized as a Fibonacci cube can be embedded into a hypercube using Fibonacci strings within the same time bound.
Print ISSN:
0178-4617
Digitale ISSN:
1432-0541
Thema:
Informatik
,
Mathematik
