Connectivity of Matching Graph of Hypercube
Connectivity of Matching Graph of Hypercube
复制标题
DOI：
10.1137/070697288
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
J. Fink
中科院分区：
文献类型：
--
作者：
J. Fink
图$G$的匹配图$\mathcal{M}（G）$具有$G$的所有完美匹配的顶点集，当对应的完美匹配的并形成Hamilton圈时，两个顶点相邻。证明了$d$维超立方体的匹配图$\mathcal{M}（Q_d）$是二部连通的。这证明了Kreweras的猜想[公牛。应用程序、16（1996），pp. 87-91]证明了图$M_d$是连通的，其中$M_d$是由$\mathcal{M}（Q_d）$通过收缩$\mathcal{M}（Q_d）$中对应于同构完美匹配的所有顶点而得到的。
The matching graph $\mathcal{M}(G)$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mathcal{M}(Q_d)$ of the $d$-dimensional hypercube is bipartite and connected for $d\ge4$. This proves Kreweras's conjecture [Bull. Inst. Combin. Appl., 16 (1996), pp. 87-91] that the graph $M_d$ is connected, where $M_d$ is obtained from $\mathcal{M}(Q_d)$ by contracting all vertices of $\mathcal{M}(Q_d)$ which correspond to isomorphic perfect matchings.