Vetenskap & teknik
Pocket
Proof of the 1-Factorization and Hamilton Decomposition Conjectures
Bela Csaba • Daniela Kuhn • Allan Lo • Deryk Osthus • Andrew Treglown
1519:-
Tillfälligt slut online – klicka på "Bevaka" för att få ett mejl så fort varan går att köpa igen.
In this paper the authors prove the following results (via a unified approach) for all sufficiently large n: (i) [1-factorization conjecture] Suppose that n is even and D2n/41. Then every D-regular graph G on n vertices has a decomposition into perfect matchings. Equivalently, (G)=D. (ii) [Hamilton decomposition conjecture] Suppose that Dn/2. Then every D-regular graph G on n vertices has a decomposition into Hamilton cycles and at most one perfect matching. (iii) [Optimal packings of Hamilton cycles] Suppose that G is a graph on n vertices with minimum degree n/2. Then G contains at least regeven (n,)/2(n2)/8 edge-disjoint Hamilton cycles. Here regeven (n,) denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree . (i) was first explicitly stated by Chetwynd and Hilton. (ii) and the special case =n/2of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.
- Format: Pocket/Paperback
- ISBN: 9781470420253
- Språk: Engelska
- Antal sidor: 164
- Utgivningsdatum: 2016-10-30
- Förlag: American Mathematical Society