Grid graphs of Catalan words

Authors:
Open Access
Publisher website
Google Scholar
Abstract
This paper fits in the intersection between two disparate areas of combinatorics. Namely, graph theory and the combinatorics of Catalan words. A Catalan word with n parts is defined as a word w = w1w2⋯wn over the set of positive integers in which w1 = 1 and 1 ≤ wk ≤ wk − 1 + 1 for k = 2, 3, …, n. In order to study the intersection of the two areas, a specific type of graph called a grid graph is defined for each Catalan word. The main thrust of the paper is investigating the degrees of vertices in grid graphs. For each of the possible fixed degrees i ∈ {1, 2, 3, 4}, we find generating functions DFi(x) where the coefficient of xn is the total number of vertices of degree i in all grid graphs with n parts.

This publication has 4 references indexed in Scilit: