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).
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom