Counting and packing Hamilton cycles in dense graphs and oriented graphs
|
Tue, 13/11/2012 14:30 |
Asaf Ferber (Tel Aviv) |
Combinatorial Theory Seminar |
SR1 |
In this talk we present a general method using permanent estimates in order to obtain results about counting and packing Hamilton cycles in dense graphs and oriented graphs. As a warm up we prove that every Dirac graph contains at least many distinct Hamilton cycles, where is the maximal degree of a spanning regular subgraph of . We continue with strengthening a result of Cuckler by proving that the number of oriented Hamilton cycles in an almost -regular oriented graph is , provided that is greater than . Last, we prove that every graph of minimum degree at least contains at least edge-disjoint Hamilton cycles, where is the maximal even degree of a spanning regular subgraph of . This proves an approximate version of a conjecture made by Osthus and Kühn.
Joint work with Michael Krivelevich and Benny Sudakov. |
|||

contains at least
many distinct Hamilton cycles, where
is the maximal degree of a spanning regular subgraph of
-regular oriented graph is
, provided that
is greater than
. Last, we prove that every graph
contains at least
edge-disjoint Hamilton cycles, where
is the maximal even degree of a spanning regular subgraph of