Share This Article:

Graph Derangements

Abstract Full-Text HTML Download Download as PDF (Size:240KB) PP. 183-191
DOI: 10.4236/ojdm.2013.34032    4,254 Downloads   6,736 Views   Citations
Author(s)    Leave a comment

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.

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.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.