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

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