OJDM  Vol.3 No.4 , October 2013
Graph Derangements
Author(s) Pete L. Clark*
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.


Cite this paper
P. Clark, "Graph Derangements," Open Journal of Discrete Mathematics, Vol. 3 No. 4, 2013, pp. 183-191. doi: 10.4236/ojdm.2013.34032.
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.

 
 
Top