Research ArticleOpen AccessGoogle Scholar indexed
Graph Derangements
University of Georgia, Athens, USA
- 1 University of Georgia, Athens, USA
Open Journal of Discrete Mathematics·Volume 03 (2013)·Pages 183–191·Published 24 October 2013·DOI10.4236/ojdm.2013.34032
Copy link · social · email
Abstract
We introduce the notion of a graph derangement, which naturally interpolates between perfect matchings and Hamilto nian 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.
KeywordsGraph Derangement Cycle Perfect Matching
- O. Knill, “A Brouwer Fixed Point Theorem for Graph Endomorphisms,” Fixed Point Theory and Applications, Vol. 2013, 2013, p. 85.
- P. R. Halmos and H. E. Vaughan, “The Marriage Problem,” American Journal of Mathematics, Vol. 72, No. 1, 1950, pp. 214-215. http://dx.doi.org/10.2307/2372148
- P. Hall, “On Representatives of Subsets,” Journal of the London Mathematical Society, Vol. 10, No. 37, 1935, pp. 26-30.
- K. Menger, “Zur Allgemeinen Kurventheorie,” Fundamenta Mathematicae, Vol. 10, 1927, pp. 96-115.
- E. Egerváry, “Matrixok Kombinatorius Tulajdonságairol,” Matematikai és Fizikai Lapok, Vol. 38, 1931, pp. 16-28.
- D. König, “Gráfok és Mátrixok,” Matematikai és Fizikai Lapok, Vol. 38, 1031, pp. 116-119.
- M. Hall Jr., “Distinct Representatives of Subsets,” Bulletin of the American Mathematical Society, Vol. 54, No. 10, 1948, pp. 922-926. http://dx.doi.org/10.1090/S0002-9904-1948-09098-X
- J. L. Kelley, “The Tychonoff Product Theorem Implies the Axiom of Choice,” Fundamenta Mathematicae, Vol. 37, No. , 1950, pp. 75-76.
- H. Cartan, “Théorie des Filtres,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 205, 1937, pp. 595-598.
- C. J. Everett and G. Whaples, “Representations of Sequences of Sets,” American Journal of Mathematics, Vol. 71, No. 2, 1949, pp. 287-293. http://dx.doi.org/10.2307/2372244
- W. T. Tutte, “The 1-Factors of Oriented Graphs,” Proceedings of the American Mathematical Society, Vol. 4, No. 6, 1953, pp. 922-931.
- J. König, “Sur la Theorie des Ensembles,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 143, 1906, pp. 110-112.
- D. König, “Theorie der Endlichen und Unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe,” Chelsea Publishing Co., New York, 1950.
- R. Rado, “Factorization of Even Graphs,” Quarterly Journal of Mathematics: Oxford Journals, Vol. 20, No. 1, 1949, pp. 95-104.
- L. Levine, “Hall’s Marriage Theorem and Hamiltonian Cycles in Graphs,” 2001.
- W. T. Tutte, “The Factorization of Linear Graphs,” Journal of the London Mathematical Society, Vol. 22, No. 2, 1947, pp. 107-111. http://dx.doi.org/10.1112/jlms/s1-22.2.107
- W. T. Tutte, “The Factorization of Locally Finite Graphs,” Canadian Journal of Mathematics, Vol. 2, No. 1, 1950, pp. 44-49. http://dx.doi.org/10.4153/CJM-1950-005-2