Premium
An Asymptotic Version of the Multigraph 1‐Factorization Conjecture
Author(s) -
Vaughan E. R.
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21629
Subject(s) - multigraph , mathematics , combinatorics , conjecture , multiplicity (mathematics) , integer (computer science) , factorization , order (exchange) , discrete mathematics , degree (music) , graph , algorithm , mathematical analysis , physics , finance , computer science , acoustics , economics , programming language
We give a self‐contained proof that for all positive integers r and all ε > 0 , there is an integer N = N ( r , ε ) such that for all n ≥ N any regular multigraph of order 2 n with multiplicity at most r and degree at least ( 1 + ε ) r n is 1‐factorizable. This generalizes results of Perković and Reed (Discrete Math 165/166 (1997), 567–578) and Plantholt and Tipnis (J London Math Soc 44 (1991), 393–400).