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

Iamthong, Kittitat and Jung, Ji-Hwan and Kitaev, Sergey (2020) Encoding labelled p-Riordan graphs by words and pattern-avoiding permutations. Graphs and Combinatorics. ISSN 0911-0119 (In Press)

[img] Text (Iamthong-etal-GC-2020-Encoding-labelled-p-Riordan-graphs-by-words-and-pattern-avoiding)
Iamthong_etal_GC_2020_Encoding_labelled_p_Riordan_graphs_by_words_and_pattern_avoiding.pdf
Accepted Author Manuscript
Restricted to Repository staff only until 1 September 2021.
Download (98kB) | Request a copy from the Strathclyde author

    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.

    Creators(s): Iamthong, Kittitat, Jung, Ji-Hwan and Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647;
    Item type:Article
    ID code:73848
    Keywords:Riordan graph, p-Riordan graph, p-Riordan word, permutation pattern, balanced word, Mathematics, Discrete Mathematics and Combinatorics, Theoretical Computer Science
    Subjects:Science > Mathematics
    Department:Faculty of Science > Computer and Information Sciences
    Faculty of Science > Mathematics and Statistics
    Depositing user: Pure Administrator
    Date deposited:15 Sep 2020 14:28
    Last modified:21 Oct 2020 04:03
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/73848
    Export data:
    CORE (COnnecting REpositories)