Perfect matchings and derangements on graphs. Issue 2 (6th January 2021)

• Record Type: Journal Article
• Authors: Bucic, Matija; Devlin, Pat; Hendon, Mo; Horne, Dru; Lund, Ben
• Is Part Of: Journal of graph theory. Volume 97:Issue 2(2021)
• Page Start: 340
• Page End: 354
• Publication Date: 2021-01-06
• Subjects: perfect matchings -- permanent -- permutations; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22658
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We show that each perfect matching in a bipartite graph G intersects at least half of the perfect matchings in G . This result has equivalent formulations in terms of the permanent of the adjacency matrix of a graph, and in terms of derangements and permutations on graphs. We give several related results and open questions.