Graph Derangements

• 作者: Pete L. Clark
• 来源期刊: 离散数学期刊(英文)
• 学科: 数学
• 关键词: GRAPH Derangement CYCLE PERFECT MATCHING
• 年，卷（期）: 2013,（4）
• 页码范围: 183-191
• 页数: 9页
• 分类号: O1

摘要

We introduce the notion of a graph derangement, which naturally interpolates between perfect matchings and Hamiltonian cycles. We give a necessary and sufficient condition for the existence of graph derangements on a locally finite graph. This result was first proved by W. T. Tutte in 1953 by applying some deeper results on digraphs. We give a new, simple proof which amounts to a reduction to the (Menger-Egerváry-K?nig-)Hall(-Hall) Theorem on transversals of set systems. We also consider the problem of classifying all cycle types of graph derangements on m × n checkerboard graphs. Our presentation does not assume any prior knowledge in graph theory or combinatorics: all definitions and proofs of needed theorems are given.