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

Kittitat Iamthong; Ji-Hwan Jung; Sergey Kitaev

doi:10.1007/s00373-020-02232-2

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

Kittitat Iamthong, Ji-Hwan Jung, Sergey Kitaev

Research output: Contribution to journal › Article › peer-review

2 Downloads (Pure)

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	https://doi.org/10.1007/s00373-020-02232-2
Publication status	Published - 31 Jan 2021

Keywords

Riordan graph
p-Riordan graph
p-Riordan word
permutation pattern
balanced word

Access to Document

10.1007/s00373-020-02232-2

Iamthong-etal-GC-2020-Encoding-labelled-p-Riordan-graphs-by-words-and-pattern-avoidingAccepted author manuscript, 96.4 KB

Cite this

@article{d6287c4f8fe44f809242feb2a5425f9b,

title = "Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations",

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.",

keywords = "Riordan graph, p-Riordan graph, p-Riordan word, permutation pattern, balanced word",

author = "Kittitat Iamthong and Ji-Hwan Jung and Sergey Kitaev",

year = "2021",

month = jan,

day = "31",

doi = "10.1007/s00373-020-02232-2",

language = "English",

volume = "37",

pages = "139--149",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

number = "1",

}

TY - JOUR

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

AU - Iamthong, Kittitat

AU - Jung, Ji-Hwan

AU - Kitaev, Sergey

PY - 2021/1/31

Y1 - 2021/1/31

N2 - 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.

AB - 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.

KW - Riordan graph

KW - p-Riordan graph

KW - p-Riordan word

KW - permutation pattern

KW - balanced word

UR - https://www.springer.com/journal/373

U2 - 10.1007/s00373-020-02232-2

DO - 10.1007/s00373-020-02232-2

M3 - Article

VL - 37

SP - 139

EP - 149

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

IS - 1

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this