2015/04/20 by Marie-Louise Bruner, Bruner, Marie-Louise, Alois Panholzer +1 · 1 citation
Computer Science · Mathematics · #05A15 #05A16 #05A19 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1504.04972
openalex publication_date 2015/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We apply the concept of parking functions to rooted labelled trees and functional digraphs of mappings (i.e., functions f : [n] → [n]) by considering the nodes as parking spaces and the directed edges as one-way streets: Each driver has a preferred parking space and starting with this node he follows the edges in the graph until he either finds a free parking space or all reachable parking spaces are occupied. If all drivers are successful we speak about a parking function for the tree or mapping. We transfer well-known characterizations of parking functions to trees and mappings. Especially, this yields bounds and characterizations of the extremal cases for the number of parking functions with m drivers for a given tree T of size n. Via analytic combinatorics techniques we study the total number Fn,m and Mn,m of tree and mapping parking functions, respectively, i.e., the number of pairs (T,s) (or (f,s)), with T a size-n tree (or f : [n] → [n] an n-mapping) and s ∈ [n]m a parking function for T (or for f) with m drivers, yielding exact and asymptotic results. We describe the phase change behaviour appearing at m=(n)/(2) for Fn,m and Mn,m, respectively, and relate it to previously studied combinatorial contexts. Moreover, we give a bijective proof of the occurring relation n Fn,m = Mn,m.