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

DOI10.1007/S00373-020-02232-2MaRDI QIDQ2657073zbMATH OpenOpenAlexFDO

Authors Kittitat Iamthong, Ji-Hwan Jung, Sergey Kitaev

Publication date 17 March 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.01410

zbMATH Keywords

permutation patternbalanced wordRiordan graph\(p\)-Riordan graph\(p\)-Riordan word

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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.

Recommendations

• Riordan graphs I: structural properties
• Counting independent sets in Riordan graphs
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Pattern avoiding permutations and independent sets in graphs
• Riordan graphs. II: Spectral properties

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• A comprehensive introduction to the theory of word-representable graphs
• Finite transition matrices for permutations avoiding pairs of length four patterns
• Hamiltonian properties of Toeplitz graphs
• On the chromatic number of Toeplitz graphs
• Patterns in permutations and words.
• Refined restricted permutations avoiding subsets of patterns of length three
• Riordan graphs I: structural properties
• Riordan graphs. II: Spectral properties
• The Riordan group
• Words and graphs

Cited in

(3)

• Riordan graphs I: structural properties
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• On graphs representable by pattern-avoiding words

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Encoding labelled \(p\)-Riordan graphs by words and pattern-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2657073)