No Detail Found!

Vertex degrees in grid graphs of permutations

Author(s)
Aubrey Blecher The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of Witwatersrand,,South Africa
Arnold Knopfmacher The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of Witwatersrand,,South Africa
Abstract
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.
Publication Details
Page(s) 8-14
Published Journal: Discrete Mathematics Letters, Volume: 16, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords
generating functions, grid graphs, permutations
References
Baril J.-L.,Kirgizov S.,Blecher A.,Knopfmacher A.,Blecher A.,Knopfmacher A.,Blecher A.,Knopfmacher A.,Bona M.,Caicedo J.,Moll B.,Callan D.,Elizalde S.,Noy M.,MacMahon P.,Combinatory Analysis,Mansour T.,Mansour T.,Shattuck M.,Mansour T.,Stanley R. .1997 .Counting pattern avoiding permutations by number of movable letters. Online J. Anal. Comb, 5 : 5-282.
0

Citations

0

Downloads

20

Views