Perfect matchings and derangements on graphs

Matija Bucic; Pat Devlin; Mo Hendon; Dru Horne; Ben Lund

doi:10.1002/jgt.22658

Perfect matchings and derangements on graphs

Matija Bucic
, Pat Devlin
, Mo Hendon
, Dru Horne
, Ben Lund

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

We show that each perfect matching in a bipartite graph (Formula presented.) intersects at least half of the perfect matchings in (Formula presented.). 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.

Original language	English (US)
Pages (from-to)	340-354
Number of pages	15
Journal	Journal of Graph Theory
Volume	97
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22658
State	Published - Jun 2021
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology
Discrete Mathematics and Combinatorics

Keywords

perfect matchings
permanent
permutations

Access to Document

10.1002/jgt.22658

Cite this

@article{bed930a9c42e4d40a31affef27057c14,

title = "Perfect matchings and derangements on graphs",

abstract = "We show that each perfect matching in a bipartite graph (Formula presented.) intersects at least half of the perfect matchings in (Formula presented.). 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.",

keywords = "perfect matchings, permanent, permutations",

author = "Matija Bucic and Pat Devlin and Mo Hendon and Dru Horne and Ben Lund",

note = "Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC",

year = "2021",

month = jun,

doi = "10.1002/jgt.22658",

language = "English (US)",

volume = "97",

pages = "340--354",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "2",

}

TY - JOUR

T1 - Perfect matchings and derangements on graphs

AU - Bucic, Matija

AU - Devlin, Pat

AU - Hendon, Mo

AU - Horne, Dru

AU - Lund, Ben

PY - 2021/6

Y1 - 2021/6

N2 - We show that each perfect matching in a bipartite graph (Formula presented.) intersects at least half of the perfect matchings in (Formula presented.). 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.

AB - We show that each perfect matching in a bipartite graph (Formula presented.) intersects at least half of the perfect matchings in (Formula presented.). 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.

KW - perfect matchings

KW - permanent

KW - permutations

UR - https://www.scopus.com/pages/publications/85099022907

UR - https://www.scopus.com/pages/publications/85099022907#tab=citedBy

U2 - 10.1002/jgt.22658

DO - 10.1002/jgt.22658

M3 - Article

AN - SCOPUS:85099022907

SN - 0364-9024

VL - 97

SP - 340

EP - 354

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

Perfect matchings and derangements on graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this