Article citationsMore>>

C. Berge, “Sur le Couplage Maximum d’un Graphe,” Comptes Rendus de l’Académie des Sciences, Paris, Vol. 247, 1958, pp. 258-259.

has been cited by the following article:

• TITLE: Graph Derangements

  AUTHORS: Pete L. Clark

  KEYWORDS: Graph Derangement Cycle Perfect Matching

  JOURNAL NAME: Open Journal of Discrete Mathematics, Vol.3 No.4, October 24, 2013

  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.