Cycle lemma, parking functions and related multigraphs

Sen Peng Eu*, Tung Shan Fu, Chun Ju Lai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


For positive integers a and b, an (a, b̄)-parking function of length n is a sequence (p1, . . ., pn) of nonnegative integers whose weakly increasing order q1 ≤ . . . ≤ qn satisfies the condition qi < a + (i - 1)b. In this paper, we give a new proof of the enumeration formula for (a, b̄)-parking functions by using of the cycle lemma for words, which leads to some enumerative results for the (a, b̄)-parking functions with some restrictions such as symmetric property and periodic property. Based on a bijection between (a, b̄)-parking functions and rooted forests, we enumerate combinatorially the (a, b̄)-parking functions with identical initial terms and symmetric (a, b̄)-parking functions with respect to the middle term. Moreover, we derive the critical group of a multigraph that is closely related to (a, b̄)-parking functions.

Original languageEnglish
Pages (from-to)345-360
Number of pages16
JournalGraphs and Combinatorics
Issue number3
Publication statusPublished - 2010
Externally publishedYes


  • Critical group
  • Cycle lemma
  • Labeled rooted forest
  • Parking function

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Cycle lemma, parking functions and related multigraphs'. Together they form a unique fingerprint.

Cite this