A Graph-Theoretic Encoding of Lucas Sequences

2015/08/01 by James Alexander, Paul Hearding · 1 citation
Physics and Astronomy · Mathematics · #Advanced Mathematical Theories and Applications #Analytic Number Theory Research #Advanced Mathematical Identities

paper · doi:10.1080/00150517.2015.12428264

Abstract

Some well-known results of Prodinger and Tichy are that the number of independent sets in the n-vertex path graph is Fn+2, and that the number of independent sets in the n-vertex cycle graph is Ln. 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.

Cited by

• On the Fibonacci-Lucas Ground State Degeneracies of the One-Dimensional Antiferromagnetic Ising Model at Criticality

Related

• A graph theoretic encoding of Lucas sequences
• Graphical sequences and plane trees
• On the independent subsets of powers of paths and cycles
• A graph polynomial for independent sets of bipartite graphs
• A study on the curling number of graph classes