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

DOI10.1016/J.DISC.2015.08.012MaRDI QIDQ501063zbMATH OpenOpenAlexFDO

Authors Pietro Codara, Ottavio M. D'Antona

Publication date 8 October 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4080

zbMATH Keywords

cycleindependent setFibonacci numberLucas numberpathFibonacci cubeLucas cubepower of graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Abstract: 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-th power of a path ordered by inclusion. For h=1 such a diagram is called a Fibonacci cube, and for h>1 we obtain a generalization of the Fibonacci cube. Consequently, we derive a generalized notion of Fibonacci sequence, called h-Fibonacci sequence. Then, we show that the number of edges of a generalized Fibonacci cube is obtained by convolution of an 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 hth power of a cycle ordered by inclusion. For h=1 such a diagram is called Lucas cube, and for h>1 we obtain a generalization of the Lucas cube. We derive then a generalized version of the Lucas sequence, called 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-Fibonacci sequence with an h-Lucas sequence.

Recommendations

• Fibonacci and Lucas \(p\)-cubes
• Some identities for the generalized Fibonacci numbers and the generalized Lucas numbers
• Generalized fibonacci cubes are mostly hamiltonian
• The degree sequence of Fibonacci and Lucas cubes
• Generalized Lucas cubes

Cites work

• scientific article; zbMATH DE number 3348111 (Why is no real title available?)
• Edge-counting vectors, Fibonacci cubes, and Fibonacci triangle
• Generalized Fibonacci cubes
• Generalized Lucas cubes
• On median nature and enumerative properties of Fibonacci-like cubes
• On the Lucas cubes
• Structural and enumerative properties of the Fibonacci cubes
• Structure of Fibonacci cubes: a survey

Cited in

(9)

• Circular embeddability of isometric words
• Proofs of two conjectures on generalized Fibonacci cubes
• Isometric words and edit distance: main notions and new variations
• Higher-order Lucas numbers
• On generalized Fibonacci cubes and unitary transforms
• Fibonacci and Lucas \(p\)-cubes
• Asymptotic properties of Fibonacci cubes and Lucas cubes
• Efficient proper embedding of a daisy cube
• On the Wiener index of generalized Fibonacci cubes and Lucas cubes

This page was built for publication: Generalized Fibonacci and Lucas cubes arising from powers of paths and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501063)