几类梯状图的完美匹配与Hamilton圈

Perfect Matching of Several Types of Ladder Graphs and Hamilton Cycles

循环梯状图CLn是由圈Cn和路p2的笛卡尔积CLn=Cn×p2(n≥3),Möbius梯状图MLn是通过梯子图Ln添加边a1bn和b1an得到。删掉CLn和MLn的一个Hamilton圈(删边不删点)后剩下的子图是它们的一个完美匹配。反之,删掉CLn和MLn的一个完美匹配后剩下的子图只要是连通的,那一定是原图的Hamilton圈。因此本文通过删除完美匹配的方法给出了Ln,CLn和MLn的所有Hamilton圈,进而通过Hamilton圈研究了完美匹配之间的关系。

The cyclic ladder graph CLn is obtained from the Cartesian product CLn=Cn×p2(n≥3) of cycles Cn and paths p2 and the Möbius ladder graph MLn is obtained by adding edges a1bn and b1an to the ladder graph Ln. The remaining subgraphs after we delete a Hamilton cycle of CLn and MLn (deleting edges without deleting points) are a perfect matching of them. Conversely, the re-maining subgraphs after deleting a perfect matching of CLn and MLn must be a Hamilton cycle of the original graph as long as they are connected. Therefore, this paper gives all Hamilton cycles of Ln, CLn and MLn by deleting perfect matching, and then investigates the relationship between perfect matching through Hamilton cycles.