Premium
Regular Graphs of High Degree are 1‐Factorizable
Author(s) -
Chetwynd A. G.,
Hilton A. J. W.
Publication year - 1985
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s3-50.2.193
Subject(s) - mathematics , conjecture , combinatorics , degree (music) , graph , disjoint sets , order (exchange) , discrete mathematics , physics , acoustics , finance , economics
It is a well‐known conjecture that if a regular graph G of order 2 n has degree d(G) satisfying d(G) ⩾ n, then G is the union of edge‐disjoint 1‐factors. It is well known that this conjecture is true for d(G) equal to 2 n —1 or 2 n —2. We show here that it is true for d(G) equal to 2 n — 3, 2 n — 4, or 2 n — 5. We also show that it is true for d(G) ⩾ 6 7 | V(G) |.
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