From G-parking functions to B-parking functions

A matching M in a multigraph G=(V,E) is said to be uniquely restricted if M is the only perfect matching in the subgraph of G induced by V(M) (i.e., the set of vertices saturated by M). For any fixed vertex x0 in G, there is a bijection from the set of spanning trees of G to the set of uniquely restricted matchings of size |V|−1 in S(G)−x0, where S(G) is the bipartite graph obtained from G by subdividing each edge in G. Thus the notion “uniquely restricted matchings of a bipartite graph H saturating all vertices in a partite set X” can be viewed as an extension of “spanning trees in a connected graph”. Motivated by this observation, we extend the notion “G-parking functions” of a connected multigraph to “B-parking functions” f:X→{−1,0,1,2,⋯} of a bipartite graph H with a bipartition (X,Y) and find a bijection ψ from the set of uniquely restricted matchings of H to the set of B-parking functions of H. We also show that for any uniquely restricted matching M in H with |M|=|X|, if f=ψ(M), then ∑x∈Xf(x) is exactly the number of elements y∈Y−V(M) which are not externally B-active with respect to M in H, where the new notion “externally B-active members with respect to M in H” is an extension of “externally active edges with respect to a spanning tree in a connected multigraph”.