Generalized Fibonacci and Lucas cubes arising from powers of paths and cycles

详细信息    查看全文

• 作者：P. Codara ; ^{codara@di.unimi.it" class="auth_mail" title="E-mail the corresponding author} ; O.M. D&rsquo ; Antona ^{dantona@di.unimi.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Independent set ; Path ; Cycle ; Power of graph ; Fibonacci cube ; Lucas cube ; Fibonacci number ; Lucas number
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 January 2016
• 年：2016
• 卷：339
• 期：1
• 页码：270-282
• 全文大小：433 K

文摘

The paper deals with some generalizations of Fibonacci and Lucas sequences, arising from powers of paths and cycles, respectively.

In the first part of the work we provide a formula for the number of edges of the Hasse diagram of the independent sets of the h$h$th power of a path ordered by inclusion. For h=1$h=1$ such a diagram is called a Fibonacci cube, and for h>1$h>1$ we obtain a generalization of the Fibonacci cube. Consequently, we derive a generalized notion of Fibonacci sequence, called h$h$-Fibonacci sequence. Then, we show that the number of edges of a generalized Fibonacci cube is obtained by convolution of an h$h$-Fibonacci sequence with itself.

In the second part we consider the case of cycles. We evaluate the number of edges of the Hasse diagram of the independent sets of the h$h$th power of a cycle ordered by inclusion. For h=1$h=1$ such a diagram is called Lucas cube, and for h>1$h>1$ we obtain a generalization of the Lucas cube. We derive then a generalized version of the Lucas sequence, called h$h$-Lucas sequence. Finally, we show that the number of edges of a generalized Lucas cube is obtained by an appropriate convolution of an h$h$-Fibonacci sequence with an h$h$-Lucas sequence.