Abstract
The notion of a p-Riordan graph generalizes that of a Riordan graph, which, in turn, generalizes the notions of a Pascal graph and a Toeplitz graph. In this paper we introduce the notion of a p-Riordan word, and show how to encode p-Riordan graphs by p-Riordan words. For special important cases of Riordan graphs (the case p=2) and oriented Riordan graphs (the case p=3) we provide alternative encodings in terms of pattern-avoiding permutations and certain balanced words, respectively. As a bi-product of our studies, we provide an alternative proof of a known enumerative result on closed walks in the cube.
| Original language | English |
|---|---|
| Pages (from-to) | 139-149 |
| Number of pages | 11 |
| Journal | Graphs and Combinatorics |
| Volume | 37 |
| Issue number | 1 |
| Early online date | 21 Sep 2020 |
| DOIs | |
| Publication status | Published - 31 Jan 2021 |
Keywords
- Riordan graph
- p-Riordan graph
- p-Riordan word
- permutation pattern
- balanced word