دانشگاه اصفهان نشریه ریاضی و جامعه 2345-6493 2 2 2017 08 23 Algebraic properties of Fibonacci and Lucas cubes خواص جبری مکعب‌های فیبوناتچی و لوکاس 43 61 20357 10.22108/msci.2017.20357 FA خدیجه فتحعلیخانی دانشگاه کاشان علی رضا اشرفی دانشکده علوم ریاضی- دانشگاه کاشان Journal Article 2015 10 05 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. ابرمکعب ‎$n$-‎بعدی ‎$Q_n$‎ گرافی است که رئوس آن رشته‌های دودویی ‎$x_1 x_2 ‎\c‎dots x_n$‎ بوده و در آن دو رأس با یکدیگر مجاورند، هرگاه به‌طور دقیق در یک مولفه متفاوت باشند و یا به عبارتی، فاصله همینگ آن‌ها یک باشد. زیرگراف‌های ابرمکعب مدلی طبیعی برای شبکه‌های ارتباطی به‌دست می‌دهند و از این رو مطالعه آن‌ها از اهمیت زیادی برخوردار است. برخی از زیرگراف‌های آن مانند مکعب‌های فیبوناتچی و مکعب‌های لوکاس از سال‌های دهه ‎50‎ میلادی بسیار مورد مطالعه ریاضی‌دانان، دانشمندان کامپیوتر و مهندسان قرار گرفته‌اند. یک مکعب فیبوناتچی زیرگرافی از ابرمکعب است به‌طوری‌که رأس‌های آن رشته‌های دودویی هستند که هیچ دو ‎1‎ متوالی ندارند. در واقع، مکعب فیبوناتچی ‎$\Gamma_n$‎ گرافی است دوبخشی که از ‎$Q_n$‎ با حذف تمام رأس‌هایی که حداقل دو ‎1‎ متوالی دارند، به‌دست می‌آید. رئوس یک مکعب لوکاس علاوه بر این خاصیت، در مکان ابتدایی و انتهایی خود همزمان ‎1‎ ندارند. هدف این مقاله مروری بر خواص جبری این مکعب‌ها است. https://math-sci.ui.ac.ir/article_20357_ed49e2cb2edc39cac847cbb239f8710d.pdf