solidot新版网站常见问题,请点击这里查看。

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$ 查看全文>>