solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看194次
Uniquely restricted matchings and an extension of G-parking functions. (arXiv:1407.1983v2 [math.CO] UPDATED)
来源于:arXiv
A matching $M$ in a graph $G$ is said to be uniquely restricted if $M$ is the
only perfect matching in the subgraph of $G$ induced by vertices saturated by
$M$. For any connected multigraph $G=(V,E)$ and a fixed vertex $x_0$ 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 the bipartite graph
$S(G)-x_0$, where $S(G)$ is obtained from $G$ by subdividing each edge in $G$.
Motivated by this observation, we extend the concept of G-parking functions of
graphs to B-parking functions $f:X\rightarrow N_0$ for any bipartite graph
$H=(X,Y)$, and establish a bijection $\psi$ from the set of uniquely restricted
matchings in $H$ to the set of B-parking functions of $H$. If $M$ is a uniquely
restricted matching of $H$ of size $|X|$ and $f=\psi(M)$, then for any $x\in
X$, $f(x)$ is interpreted by the number of some elements $y\in Y$ which are not
saturated by $M$ and are not externally B-active with respect to $M$ in $H$ 查看全文>>