Graph Derangements

Pete L. Clark

REVIEW

Graph Derangements

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1306.6436 v2 pith:A3UML27H submitted 2013-06-27 math.CO

Graph Derangements

Pete L. Clark This is my paper

classification math.CO

keywords graphderangementsgivehallamountsapplyingassumecheckerboard

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original 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-Egervary-Konig-)Hall(-Hall) Theorem on transversals of set systems. Finally, we consider the problem of classifying all cycle types of graph derangements on m x 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.

Graph Derangements

discussion (0)