论文标题
笛卡尔产物的完美匹配和大麻
Perfect matchings and Hamiltonicity in the Cartesian product of cycles
论文作者
论文摘要
图$ g $的配对是完整图的完美匹配，其顶点集与$ g $相同。如果每种$ g $的配对都可以扩展到仅使用$ g $的边缘的基础完整图的汉密尔顿周期，则$ g $具有pH-property。 PMH-Property是一个较弱的财产，$ G $的每个完美匹配都可以扩展到$ g $的汉密尔顿周期。为了表征所有具有pH值得ph-杂质的4个规则图，我们回答了Alahmadi等人在2015年提出的一个问题。通过证明$ c_p \ square c_p \ square c_q $在$ p $和$ q $ vertices上的两个周期的c_q $没有pmh-property，除了$ c_4 \ square c_4 $，这是ph-property。
A pairing of a graph $G$ is a perfect matching of the complete graph having the same vertex set as $G$. If every pairing of $G$ can be extended to a Hamiltonian cycle of the underlying complete graph using only edges from $G$, then $G$ has the PH-property. A somewhat weaker property is the PMH-property, whereby every perfect matching of $G$ can be extended to a Hamiltonian cycle of $G$. In an attempt to characterise all 4-regular graphs having the PH-property, we answer a question made in 2015 by Alahmadi et al. by showing that the Cartesian product $C_p\square C_q$ of two cycles on $p$ and $q$ vertices does not have the PMH-property, except for $C_4\square C_4$ which is known to have the PH-property.
