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

DOI10.1016/J.DISC.2015.08.012zbMATH Open1322.05105arXiv1410.4080OpenAlexW1642364198MaRDI QIDQ501063FDOQ501063

Authors: Pietro Codara, Ottavio M. D'Antona 

Publication date: 8 October 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Structure of Fibonacci cubes: a survey
• On the Lucas cubes
• On median nature and enumerative properties of Fibonacci-like cubes
• Generalized Fibonacci cubes
• Structural and enumerative properties of the Fibonacci cubes
• Generalized Lucas cubes
• Edge-counting vectors, Fibonacci cubes, and Fibonacci triangle
• Title not available (Why is that?)

Cited In (9)

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

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)