Encoding Labelled p -Riordan Graphs by Words and Pattern-Avoiding Permutations
- PDF / 332,802 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 169 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Encoding Labelled p-Riordan Graphs by Words and PatternAvoiding Permutations Kittitat Iamthong1 • Ji-Hwan Jung2
•
Sergey Kitaev1
Received: 11 December 2019 / Revised: 3 September 2020 / Accepted: 9 September 2020 Springer Japan KK, part of Springer Nature 2020
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
Mathematics Subject Classification 05A05 05A15
1 Introduction The interplay between words and graphs has been investigated in the literature repeatedly, as discussed in [7] focusing on word-representable graphs that are also surveyed in [6]. Various ways to encode graphs in terms of words often allow to & Ji-Hwan Jung [email protected] Kittitat Iamthong [email protected] Sergey Kitaev [email protected] 1
Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, UK
2
Center for Educational Research, Seoul National University, Seoul 08826, Republic of Korea
123
Graphs and Combinatorics
reveal and describe various useful properties of graphs, such as classes where difficult algorithmic problems become easy. The Pru¨fer sequence giving a fascinating relationship between labelled trees with n vertices and sequences of length n 2 made of the elements of the set ½n :¼ f1; 2; . . .; ng, is a classical example showing the importance of words for graph enumeration. In this paper we study encoding of so-called labelled p-Riordan graphs by certain words, and also consider encoding a particular important case of p ¼ 2 (labelled Riordan graphs) by certain pattern-avoiding permutations extensively studied in the literature [5]. We consider only labelled graphs, so the word ‘‘labelled’’ is omitted throughout this paper. We begin with introducing the notions of interest. Riordan graphs. A Riordan matrix [13] L ¼ ½‘ij i;j 0 generated by two formal P1 P n n power series g ¼ 1 n¼0 gn t and f ¼ n¼1 fn t in Z½½t is denoted as (g, f) and defined as an infinite lower triangular matrix whose j-th column generating function P is gf j , i.e. ‘ij ¼ ½ti gf j where ½tk n 0 an tn ¼ ak . If g0 6¼ 0 and f1 6¼ 0 then the Riordan matrix is called proper. A simple graph G of order n is said to be a Riordan graph if the adjacency matrix A(G) can be expressed as AðGÞ ðtg; f Þn þ ðtg; f ÞTn ðmod 2Þ
ð1Þ
for some generating functi
Data Loading...
