A simpler proof for vertex-pancyclicity of squares of connected claw-free graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Alexandru I. Tomescu ; ^{alexandru.tomescu@uniud.it} ; ^{alexandru.tomescu@gmail.com}
• 关键词：Claw-free graph ; Graph square ; Vertex-pancyclicity ; Perfect matching
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 August, 2012
• 卷：312
• 期：15
• 页码：2388-2391
• 文件大小：194 K

摘要

We give a simpler proof of the well-known result of Matthews and Sumner stating that squares of connected claw-free graphs are vertex-pancyclic. Contrary to the previous proof, our approach does not resort to Fleischner鈥檚 result stating that, when restricted to squares of graphs, vertex-pancyclicity and Hamiltonicity are equivalent. The same proof idea already yielded that connected claw-free graphs of even order have a perfect matching, which is another result of Sumner. We conclude by observing that this proof identifies a larger collection of graphs for which the two properties in question hold.