Abstract
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.
Similar content being viewed by others
References
Aurenhammer, F., Hagauer, J.: Recognizing binary Hamming graphs in O(n 2logn) time. Math. Syst. Theory 28, 387–395 (1995)
Cabello, S., Eppstein, D., Klavžar, S.: The Fibonacci dimension of a graph. Electron. J. Comb. 18, P55 (2011)
Eppstein, D.: Recognizing partial cubes in quadratic time. J. Graph Algorithms Appl. 15, 269–293 (2011)
Hammack, R., Imrich, W., Klavžar, S.: Handbook of Product Graphs, 2nd edn. CRC Press, Boca Raton (2011)
Hsu, W.-J.: Fibonacci cubes—a new interconnection technology. IEEE Trans. Parallel Distrib. Syst. 4, 3–12 (1993)
Jha, P.K., Slutzki, G.: Convex-expansions algorithms for recognition and isometric embedding of median graphs. Ars Comb. 34, 75–92 (1992)
Klavžar, S.: On median nature and enumerative properties of Fibonacci-like cubes. Discrete Math. 299, 145–153 (2005)
Klavžar, S.: Structure of Fibonacci cubes: a survey. J. Comb. Optim. 25, 505–522 (2013)
Klavžar, S., Mollard, M., Petkovšek, M.: The degree sequence of Fibonacci and Lucas cubes. Discrete Math. 311, 1310–1322 (2011)
Munarini, E., Perelli Cippo, C., Zagaglia Salvi, N.: On the Lucas cubes. Fibonacci Q. 39, 12–21 (2001)
Taranenko, A., Vesel, A.: Fast recognition of Fibonacci cubes. Algorithmica 49, 81–93 (2007)
Winkler, P.: Isometric embeddings in products of complete graphs. Discrete Appl. Math. 7, 221–225 (1984)
Acknowledgements
The work is supported by the Ministry of Science of Slovenia under the grant 0101-P-297.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vesel, A. Linear Recognition and Embedding of Fibonacci Cubes. Algorithmica 71, 1021–1034 (2015). https://doi.org/10.1007/s00453-013-9839-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-013-9839-3