خواص جبری مکعب‌های فیبوناتچی و لوکاس

نوع مقاله: مقاله علمی-ترویجی

نویسندگان

1 دانشگاه کاشان

2 دانشکده علوم ریاضی- دانشگاه کاشان

چکیده

ابرمکعب ‎$n$-‎بعدی ‎$Q_n$‎ گرافی است که رئوس آن رشته‌های دودویی ‎$x_1 x_2 ‎\c‎dots x_n$‎ بوده و در آن دو رأس با یکدیگر مجاورند، هرگاه به‌طور دقیق در یک مولفه متفاوت باشند و یا به عبارتی، فاصله همینگ آن‌ها یک باشد. زیرگراف‌های ابرمکعب مدلی طبیعی برای شبکه‌های ارتباطی به‌دست می‌دهند و از این رو مطالعه آن‌ها از اهمیت زیادی برخوردار است. برخی از زیرگراف‌های آن مانند مکعب‌های فیبوناتچی و مکعب‌های لوکاس از سال‌های دهه ‎50‎ میلادی بسیار مورد مطالعه ریاضی‌دانان، دانشمندان کامپیوتر و مهندسان قرار گرفته‌اند. یک مکعب فیبوناتچی زیرگرافی از ابرمکعب است به‌طوری‌که رأس‌های آن رشته‌های دودویی هستند که هیچ دو ‎1‎ متوالی ندارند. در واقع، مکعب فیبوناتچی ‎$\Gamma_n$‎ گرافی است دوبخشی که از ‎$Q_n$‎ با حذف تمام رأس‌هایی که حداقل دو ‎1‎ متوالی دارند، به‌دست می‌آید. رئوس یک مکعب لوکاس علاوه بر این خاصیت، در مکان ابتدایی و انتهایی خود همزمان ‎1‎ ندارند. هدف این مقاله مروری بر خواص جبری این مکعب‌ها است.

کلیدواژه‌ها


[3] م. ر. درفشه، مقدمه‌ای بر نظریه گروه‌ها، تهران، نشر علوم پایه، ‎1369‎.

[2] خ. فتحعلیخانی، خواص جبری و متریک ابرمکعب و برخی زیرگراف‌های آن، رساله دکتری، دانشگاه کاشان، ‎1394‎.

 

[3] خ. فتحعلیخانی، ع. ر.اشرفی، خواص متریک و ترکیبیاتی مکعب‌های فیبوناتچی و لوکاس، پذیرش شده در مجله محاسبات نرم، ‎1395‎.

 

[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.