A graph-theoretic encoding of Lucas sequences

MaRDI QIDQ4689723zbMATH OpenFDO

Authors James Alexander, Paul Hearding

Publication date 17 October 2018

Full work available at URL https://arxiv.org/abs/1501.00061, https://www.fq.math.ca/Papers1/53-3/AlexHeard01232015.pdf

zbMATH Keywords

Dickson polynomials of first and second kindgraph-theoretic encodingLucas sequences of first and second kind

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Polynomials over finite fields (11T06)

Abstract: Some well-known results of Prodinger and Tichy are that the number of independent sets in the $n$-vertex path graph is $F_{n+2}$, and that the number of independent sets in the $n$-vertex cycle graph is $L_n$. We generalize these results by introducing new classes of graphs whose independent set structures encode the Lucas sequences of both the first and second kind. We then use this class of graphs to provide new combinatorial interpretations of the terms of Dickson polynomials of the first and second kind.

Recommendations

• Fibonacci numbers and Lucas numbers in graphs
• Generalized sequences and \(k\)-independent sets in graphs
• Some identities for the generalized Fibonacci numbers and the generalized Lucas numbers
• On the Lucas cubes
• A note on Fibonacci and Lucas number of domination in path

Cited in

(4)

• A method for computing Lucas sequences
• An Introduction to Coding Sequences of Graphs
• Hosoya index of thorny polymers
• Colourability of graphs representing the Lucas series modulo \(t\)

This page was built for publication: A graph-theoretic encoding of Lucas sequences

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