TITLE:
Graph Derangements
AUTHORS:
Pete L. Clark
KEYWORDS:
Graph Derangement Cycle Perfect Matching
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.4,
October
24,
2013
ABSTRACT:
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.