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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Cheon, G.-S., Jung, J.-H., Kitaev, S., Mojallal, S.A.: Riordan graphs I: structural properties. Linear Algebra Appl. 579, 89–135 (2019)
Cheon, G.-S., Jung, J.-H., Kitaev, S., Mojallal, S.A.: Riordan graphs II: spectral properties. Linear Algebra Appl. 575, 174–215 (2019)
Jung, J.-H.: Diameter of io-decomposable Riordan graphs of the Bell type. arXiv:1901.11156
Jung, J.-H.: Oriented Riordan graphs and their fractal property. arXiv:2009.01677
Kitaev, S.: Patterns in Permutations and Words. Springer, New York (2011)
Kitaev, S.: A Comprehensive introduction to the theory of word-representable graphs. In: Developments in Language Theory: 21st International Conference, DLT, Liege, 7–11 Aug 2017. Lecture Notes in Computer Science, vol. 10396, pp. 36–67 (2017)
Kitaev, S., Lozin, V.: Words and Graphs. Springer, Berlin (2015)
Kremer, D., Shiu, W.C.: Finite transition matrices for permutations avoiding pairs of length four patterns. Discret. Appl. Math. 268, 171–183 (2003)
Mansour, T., Robertson, A.: Refined restricted permutations avoiding subsets of patterns of length three. Ann. Combin. 6(3–4), 407–418 (2002)
Nicoloso, S., Piestropaoli, U.: On the chromatic number of Toeplitz graphs. Discret. Appl. Math. 164, 286–296 (2014)
Reyzin, L.: Mathoverflow, number of closed walks on an n-cube. https://www.mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube
Sloane, N.J.A.: The on-line encyclopedia of integer sequences. http://www.oeis.org
Shapiro, L.W., Getu, S., Woan, W.-J., Woodson, L.C.: The Riordan group. Discret. Appl. Math. 34, 229–239 (1991)
van Dal, R., Tijssen, G., Tuza, Z., van der Veen, J., Zamfirescu, C., Zamfirescu, T.: Hamiltonian properties of Toeplitz graphs. Discret. Math. 159, 69–81 (1996)
Acknowledgements
The work of the second author was supported by the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education of Korea (NRF-2019R1I1A1A01044161).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Iamthong, K., Jung, JH. & Kitaev, S. Encoding Labelled p-Riordan Graphs by Words and Pattern-Avoiding Permutations. Graphs and Combinatorics 37, 139–149 (2021). https://doi.org/10.1007/s00373-020-02232-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-020-02232-2