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

DOI10.1007/S00373-020-02232-2zbMATH Open1459.05002arXiv2009.01410OpenAlexW3085046325MaRDI QIDQ2657073FDOQ2657073

Authors: Kittitat Iamthong, Ji-Hwan Jung, Sergey Kitaev 

Publication date: 17 March 2021

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

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.

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

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

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)

Cites Work

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

Cited In (3)

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

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)