Algebraic properties of Fibonacci and Lucas cubes

Document Type : Research Paper

Authors

University of Kashan

Abstract

The ‎$n$-dimensional hypercube $Q_n$ is a graph with vertices corresponding to binary strings $x_1 x_2 ‎\c‎dots x_n$, where two vertices are adjacent if and only if they differ in exactly one component, or in other words, their Hamming distance is one. Subgraphs of hypercubes provide a natural model for communication networks, making their study highly important. Some subgraphs, such as Fibonacci cubes and Lucas cubes, have been extensively studied by mathematicians, computer scientists, and engineers since the 1950s. A Fibonacci cube is a subgraph of a hypercube whose vertices correspond to binary strings with no consecutive ones. In essence, the Fibonacci cube $\Gamma_n$ is a bipartite graph obtained from $Q_n$ by removing all vertices that have at least two consecutive ones. The vertices of a Lucas cube, in addition to the property mentioned, do not simultaneously have ones at both the beginning and end. The goal of this article is to provide an overview of the algebraic properties of these cubes.

Keywords

References

[1] M. Derefsh, An introduction to group theory, Tehran University Press, 3rd ed., 2009.
[2] K. Fathalikhani, Algebraic and metrical properties of a hypercube and some subgraphs of it, Phd Thesis, Kashan University, 2015.
 
[3] K. Fathalikhani and A. R. Ashrafi, Metric and Combinatorial Properties of Fibonacci and Lucas cubes. Soft Computing Journal, 2021; 5(2016) 78-100.
 
[4] A. R. Ashrafi, J. Azarija, Kh. Fathalikhani, S. Klavžar and M. Petkovšek, Vertex and edge orbits of Fibonacci and Lucas cubes, Ann. Comb., 20 (2016) 209–229.
 
[5] A. R. Ashrafi, J. Azarija, A. Babai, Kh. Fathalikhani and S. Klavžar, The (non-)existence of perfect codes in Fibonacci cubes, Inform. Process. Lett., 116 (2016) 387–390.

[6] B. Brešar, P. Dorbec, S. Klavžar and M. Mollard, Hamming polynomials and their partial derivatives, European J. Combin., 28 (2007) 1156–1162.

[7] B. Brešar, S. Klavžar and R. Škrekovski, On cube-free median graphs, Discrete Math., 307 (2007) 345–351.

[8] B. Brešar, S. Klavžar and R. Škrekovski, Roots of cube polynomials of median graphs, J. Graph Theory, 52 (2006) 37–50.

[9] B. Brešar, S. Klavžar and R. Škrekovski, The cube polynomial and its derivatives: the case of median graphs, Electron. J. Combin., 10 (2003) Research Paper 3, 11 pp.

[10] S. Cabello, D. Eppstein and S. Klavžar, The Fibonacci dimension of a graph, Electron. J. Combin., 18 (2011) Research Paper 55, 23 pp.

[11] A. Castro, S. Klavžar, M. Mollard and Y. Rho, On the domination number and the ۲ -packing number of Fibonacci cubes and Lucas cubes, Comput. Math. Appl., 61 (2011) 2655–2660.

[12] B. Cong, S. Zheng and S. Sharma, On simulations of linear arrays, rings and 2d meshes on fibonacci cube networks, In Processings of the 7th International Parallel Processing Symphosium, (1993) 747–751.

[13] M. R. Darafsheh, Computation of topological indices of some graphs, Acta Appl. Math., 110 (2010) 1225–1235.

[14] E. Dedó, D. Torri and N. Zagaglia Salvi, The observability of the Fibonacci and the Lucas cubes, Discrete Math., 255 (2002) 55–63.

[15] P. Gregor, Recursive fault-tolerance of Fibonacci cube in hypercubes, Descrete Math., 306 (2006) 1327–1341.

[16] H. Hosoya, Fibonacci triangle, Fibonacci Quart., 14 (1976) 173–179.

[17] W.-J. Hsu, Fibonacci cubes- a new interconnection technology, IEEE Trans. Parallel Distrib. Syst., 4 (1993) 3–12.

[18] W.-J. Hsu, C. V. Page and J.-S. Liu, Fibonacci cubes-a class of self-similar graphs, Fibonacci Quart., 31 (1993) 65–72.

[19] W. Imrich and S. Klavžar, Product graphs: structure and recognition, Wiley-Interscience, New York, 2000.

[20] S. Klavžar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25 (2013) 505–522.

[21] S. Klavžar, On median nature and enumerative properties of Fibonacci-like cubes, Discrete Math., 299 (2005) 145–153.

[22] S. Klavžar and M. Mollard, Cube polynomial of Fibonacci and Lucas cubes, Acta Appl. Math., 117 (2012) 93–105.

[23] S. Klavžar and I. Peterin, Edge-counting vectors, Fibonacci cubes and Fibonacci triangle, Publ. Math. Debrecen., 71 (2007) 267–278.

[24] M. Kovše, Complexity of phylogenetic networks: counting cubes in median graphs and related problems, In Analysis of Complex Networks: From Biology to Linguistics, WILEY-VCH, Weinheim, (2009) 323–350.

[25] M. Mollard, Maximal hypercubes in Fibonacci and Lucas cubes, Discrete Appl. Math., 160 (2012) 2479–2483.

[26] E. Munarini, C. Perelli Cippo and N. Zagaglia Salvi, On the Lucas cubes, Fibinacci Quart., 39 (2001) 12–21.

[27] E. Munarini and N. Zagaglia Salvi, Structural and enumerative properties of the Fibonacci cubes, Discrete Math., 255 (2002) 317–324.

[28] W. E. Patten and S. W. Golomb, Elementary Problems and Solutions: Solutions: E1470, Amer. Math. Monthly., 69 (1962) 61–62.

[29] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org, 2015.

[30] R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Graph theory and its applications:East and West (Jinan, 1986), 500–535, Ann. New York Acad. Sci., 576, New York Acad. Sci., New York, 1989.

[31] V. G. Vizing, The Cartesian product of graphs, Vychisl. Sistemy., 9 (1963) 30–43.

[32] N. Zagaglia Salvi, The automorphism group of the Lucas semilattice, Bull. Inst. Combin. Appl., 34 (2002) 11–15.

[33] H. Zhang, L. Ou and H. Yao, Fibonacci-like cubes as Z -transformation graphs, Discrete Math., 309 (2009) 1284–1293.
Mathematics and Society
Volume 2, Issue 2
June 2017
Pages 43-61

Files

History

  • Receive Date: 05 October 2015
  • Revise Date: 08 June 2016
  • Accept Date: 17 July 2016
  • Publish Date: 23 August 2017

Share

How to cite

Statistics