Vertex degrees in grid graphs of permutations
Aubrey Blecher, Arnold Knopfmacher · Discrete Mathematics Letters · 2025
A permutation of length n is defined as a finite sequence a1, a2, . . ., an of distinct positive integers called parts, where for 1 ≤ i ≤ n, the ith part ai belongs to the set {1, 2, . . ., n}.In order to study permutations in the context of graph theory, a specific type of graph called a grid graph is defined for each permutation.For each possible fixed degree i ∈ {1, 2, 3, 4}, a multivariate generating function is determined to track the total number of vertices of each degree in permutations of length n.A formula is also provided for the total number of horizontal edges in grid graphs corresponding to permutations of length n.