Graph Derangements

Pete L. Clark

University of Georgia, Athens, USA.

DOI: 10.4236/ojdm.2013.34032                

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.

Keywords

Graph Derangement Cycle Perfect Matching

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	O. Knill, “A Brouwer Fixed Point Theorem for Graph Endomorphisms,” Fixed Point Theory and Applications, Vol. 2013, 2013, p. 85.
[2]	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
[3]	P. Hall, “On Representatives of Subsets,” Journal of the London Mathematical Society, Vol. 10, No. 37, 1935, pp. 26-30.
[4]	K. Menger, “Zur Allgemeinen Kurventheorie,” Fundamenta Mathematicae, Vol. 10, 1927, pp. 96-115.
[5]	E. Egerváry, “Matrixok Kombinatorius Tulajdonságairol,” Matematikai és Fizikai Lapok, Vol. 38, 1931, pp. 16-28.
[6]	D. König, “Gráfok és Mátrixok,” Matematikai és Fizikai Lapok, Vol. 38, 1031, pp. 116-119.
[7]	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
[8]	J. L. Kelley, “The Tychonoff Product Theorem Implies the Axiom of Choice,” Fundamenta Mathematicae, Vol. 37, No. , 1950, pp. 75-76.
[9]	H. Cartan, “Théorie des Filtres,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 205, 1937, pp. 595-598.
[10]	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
[11]	W. T. Tutte, “The 1-Factors of Oriented Graphs,” Proceedings of the American Mathematical Society, Vol. 4, No. 6, 1953, pp. 922-931.
[12]	J. König, “Sur la Theorie des Ensembles,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 143, 1906, pp. 110-112.
[13]	D. König, “Theorie der Endlichen und Unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe,” Chelsea Publishing Co., New York, 1950.
[14]	R. Rado, “Factorization of Even Graphs,” Quarterly Journal of Mathematics: Oxford Journals, Vol. 20, No. 1, 1949, pp. 95-104.
[15]	L. Levine, “Hall’s Marriage Theorem and Hamiltonian Cycles in Graphs,” 2001.
[16]	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
[17]	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
[18]	C. Berge, “Sur le Couplage Maximum d’un Graphe,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 247, 1958, pp. 258-259.