Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations

Iamthong, Kittitat and Jung, Ji-Hwan and Kitaev, Sergey (2021) Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations. Graphs and Combinatorics, 37 (1). pp. 139-149. ISSN 0911-0119 (https://doi.org/10.1007/s00373-020-02232-2)

[thumbnail of Iamthong-etal-GC-2020-Encoding-labelled-p-Riordan-graphs-by-words-and-pattern-avoiding]
Preview
 Text. Filename: Iamthong_etal_GC_2020_Encoding_labelled_p_Riordan_graphs_by_words_and_pattern_avoiding.pdf
Accepted Author Manuscript
Download (98kB)| Preview

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.

CORE (COnnecting REpositories)