Hamilton decompositions of regular expanders: Applications

Alon, 1994, The algorithmic aspects of the regularity lemma, J. Algorithms, 16, 80, 10.1006/jagm.1994.1005 Alon, 2004, Algorithms with large domination ratio, J. Algorithms, 50, 118, 10.1016/j.jalgor.2003.09.003 Alon, 2004, Testing subgraphs in directed graphs, J. Comput. System Sci., 69, 354, 10.1016/j.jcss.2004.04.008 Alon, 2000 Alspach, 2012, Paley graphs have Hamilton decompositions, Discrete Math., 312, 113, 10.1016/j.disc.2011.06.003 Auerbach, 1976, On decompositions of r-partite graphs into edge-disjoint Hamiltonian circuits, Discrete Math., 14, 265, 10.1016/0012-365X(76)90039-X Ben-Shimon, 2011, On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs, SIAM J. Discrete Math., 25, 1176, 10.1137/110821299 Bollobás, 1985 Bollobás, 1985, On matchings and Hamiltonian cycles in random graphs, vol. 118, 23 Bondy, 1995, Basic Graph Theory: Paths and Circuits, vol. 1, 3 Christofides, 2012, Finding Hamilton cycles in robustly expanding digraphs, J. Graph Algorithms Appl., 16, 337, 10.7155/jgaa.00261 Christofides, 2012, Edge-disjoint Hamilton cycles in graphs, J. Combin. Theory Ser. B, 102, 1035, 10.1016/j.jctb.2011.10.005 B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case, preprint. B. Csaba, D. Kühn, A. Lo, D. Osthus, A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures III: approximate decompositions, preprint. A. Ferber, M. Krivelevich, B. Sudakov, Counting and packing Hamilton cycles in dense graphs and oriented graphs, preprint. Frieze, 2005, On packing Hamilton cycles in ε-regular graphs, J. Combin. Theory Ser. B, 94, 159, 10.1016/j.jctb.2004.12.003 Frieze, 2008, On two Hamilton cycle problems in random graphs, Israel J. Math., 166, 221, 10.1007/s11856-008-1028-8 Glover, 1997, The travelling salesman problem: New solvable cases and linkages with the development of approximation algorithms, J. Oper. Res. Soc., 48, 502, 10.1057/palgrave.jors.2600392 Gutin, 2001, TSP tour domination and Hamilton cycle decompositions of regular graphs, Oper. Res. Lett., 28, 107, 10.1016/S0167-6377(01)00053-0 S.G. Hartke, R. Martin, T. Seacrest, Relating minimum degree and the existence of a k-factor, research manuscript. S.G. Hartke, T. Seacrest, Random partitions and edge-disjoint Hamilton cycles, preprint. Hetyei, 1975, On Hamiltonian circuits and 1-factors of the regular complete n-partite graphs, Acta Acad. Pedagog, Civitate Press Ser., 19, 5 Jackson, 1979, Edge-disjoint Hamilton cycles in regular graphs of large degree, J. Lond. Math. Soc., 19, 13, 10.1112/jlms/s2-19.1.13 Jackson, 1981, Long paths and cycles in oriented graphs, J. Graph Theory, 5, 145, 10.1002/jgt.3190050204 Janson, 2000 Keevash, 2009, An exact minimum degree condition for Hamilton cycles in oriented graphs, J. Lond. Math. Soc., 79, 144, 10.1112/jlms/jdn065 Kelly, 2008, A Dirac-type result on Hamilton cycles in oriented graphs, Combin. Probab. Comput., 17, 689, 10.1017/S0963548308009218 Kim, 2001, Random matchings which induce Hamilton cycles, and Hamiltonian decompositions of random regular graphs, J. Combin. Theory Ser. B, 81, 20, 10.1006/jctb.2000.1991 Knox, 2012, Approximate Hamilton decompositions of random graphs, Random Structures Algorithms, 40, 133, 10.1002/rsa.20365 Knox, 2013, Edge-disjoint Hamilton cycles in random graphs, Random Structures Algorithms Knox, 2013, Embedding spanning bipartite graphs of small bandwidth, Combin. Probab. Comput., 22, 71, 10.1017/S0963548312000417 Krivelevich, 2012, Optimal packings of Hamilton cycles in sparse random graphs, SIAM J. Discrete Math., 26, 964, 10.1137/110849171 Krivelevich, 2001, Random regular graphs of high degree, Random Structures Algorithms, 18, 346, 10.1002/rsa.1013 Kühn, 2013, Optimal packings of Hamilton cycles in graphs of high minimum degree, Combin. Probab. Comput., 22, 394, 10.1017/S0963548312000569 D. Kühn, A. Lo, D. Osthus, Proof of the 1-factorization and Hamilton decomposition conjectures IV: exceptional systems for the two cliques case, preprint. D. Kühn, A. Lo, D. Osthus, A. Treglown, Proof of the 1-factorization and Hamilton decomposition conjectures I: the two cliques case, preprint. Kühn, 2009, Embedding large subgraphs into dense graphs, vol. 365, 137 Kühn, 2012, A survey on Hamilton cycles in directed graphs, European J. Combin., 33, 750, 10.1016/j.ejc.2011.09.030 Kühn, 2013, Hamilton decompositions of regular expanders: a proof of Kellyʼs conjecture for large tournaments, Adv. Math., 237, 62, 10.1016/j.aim.2013.01.005 Kühn, 2010, Hamiltonian degree sequences in digraphs, J. Combin. Theory Ser. B, 100, 367, 10.1016/j.jctb.2009.11.004 Kühn, 2010, Hamilton decompositions of regular tournaments, Proc. Lond. Math. Soc., 101, 303, 10.1112/plms/pdp062 Moon, 1968 Nash-Williams, 1970, Hamiltonian lines in graphs whose vertices have sufficiently large valencies, 813 Nash-Williams, 1971, Hamiltonian arcs and circuits, vol. 186, 197 Ng, 1997, Hamilton decompositions of regular complete regular multipartite digraphs, Discrete Math., 177, 179, 10.1016/S0012-365X(97)00017-4 Osthus, 2013, Approximate Hamilton decompositions of regular robustly expanding digraphs, SIAM J. Discrete Math., 27, 1372, 10.1137/120880951 Perkovic, 1997, Edge coloring regular graphs of high degree, Discrete Math., 165/166, 567, 10.1016/S0012-365X(96)00202-6 Szemerédi, 1978, Regular partitions of graphs, vol. 260, 399 Thomassen, 1979, Long cycles in digraphs with constraints on the degrees, vol. 38, 211 Tillson, 1980, A Hamiltonian decomposition of K2m⁎, 2m⩾8, J. Combin. Theory Ser. B, 29, 68, 10.1016/0095-8956(80)90044-1