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

فتحعلیخانی, خدیجه; اشرفی, علی رضا

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

نویسندگان

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

چکیده

یک ابرمکعب n-‎بعدی ‎Q_n‎ گرافی است که رأس‌های آن n-‎تایی‌های دودویی هستند و دو ر‏أس با یکدیگر مجاورند، هرگاه به‌طور دقیق در یک مولفه متفاوت باشند. ابرمکعب‌ها و نیز زیرگراف‌های آن‌ها به دلیل کاربردهای فراوان در علوم مختلف، به‌خصوص در علم کامپیوتر، بسیار مورد توجه دانشمندان مختلف بوده‌اند. برخی از زیرگراف‌های آن‌ها مانند مکعب‌های فیبوناتچی و مکعب‌های لوکاس در شبکه‌های ارتباطی به‌کار می‌روند. ما در این مقاله، پس از بیان مختصری از کاربردهای این دو دسته از مکعب‌ها، به ‏گزارش یافته‌های ‏متریک و ترکیبیاتی خود و دیگران درمورد آن‌ها می‌پردازیم. سپس‏، برخی مسائل باز را در این رابطه که خود به بررسی آن‌ها پرداخته و نتایجی یافته‌ایم‏، مطرح می‌کنیم. در ادامه‏، نرم‌افزار ‎‎‎Sage‎‎‏ را که در محاسبات مربوط به این مکعب‌ها در ابعاد بالا به‌کار می‌روند، به‌طور خلاصه و گذرا معرفی می‌کنیم.

کلیدواژه‌ها

عنوان مقاله [English]

Metric and Combinatorial Properties of Fibonacci and Lucas cubes

نویسندگان [English]

Khadijeh Fathalikhani
Ali Reza Ashrafi

چکیده [English]

An n-dimensional hypercube, Q_n, is a graph in which vertices are binary strings of length n where two vertices are adjacent if they differ in exactly one coordinate. Hypercubes and their subgraphs have a lot of applications in different fields of science, specially in computer science. This is the reason why they have been investigated by many authors during the years. Some of their subgraphs named Fibonacci cubes and Lucas cubes are very important and are useful in interconnection networks. In this paper, after introducing these cubes, we report their metric and combinatorial properties done by different authors. Then, we present some open problems that we have been encountered during our research regarding these cubes. Finally, we briefly introduce the software named Sage which is very applicable in the calculations for theses cubes in high dimensions.

کلیدواژه‌ها [English]