Abstract
The notion of a Riordan graph was introduced recently, and it is a far-reaching generalization of the well-known Pascal graphs and Toeplitz graphs. However, apart from a certain subclass of Toeplitz graphs, nothing was known on independent sets in Riordan graphs.
In this paper, we give exact enumeration and lower and upper bounds
for the number of independent sets for various classes of Riordan
graphs. Remarkably, we offer a variety of methods to solve the
problems that range from the structural decomposition theorem to
methods in combinatorics on words. Some of our results are valid for
any graph.
In this paper, we give exact enumeration and lower and upper bounds
for the number of independent sets for various classes of Riordan
graphs. Remarkably, we offer a variety of methods to solve the
problems that range from the structural decomposition theorem to
methods in combinatorics on words. Some of our results are valid for
any graph.
| Original language | English |
|---|---|
| Article number | 112043 |
| Number of pages | 20 |
| Journal | Discrete Mathematics |
| Volume | 343 |
| Issue number | 11 |
| Early online date | 3 Jul 2020 |
| DOIs | |
| Publication status | Published - 30 Nov 2020 |
Keywords
- Riordan graph
- Toeplitz graph
- independent set
- pattern avoiding sequence
- Fibonacci number
- Pell number
- Hamiltonian path
