Cycle Partitions in Dense Regular Digraphs and Oriented Graphs

Lo, Allan  ; Patel, Viresh ; Yıldız, Mehmet Akif 

Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e79

Résumé

A conjecture of Jackson from 1981 states that every d-regular oriented graph on n vertices with $n\leq 4d+1$ is Hamiltonian. We prove this conjecture for sufficiently large n. In fact we prove a more general result that for all $\alpha>0$, there exists $n_0=n_0(\alpha )$ such that every d-regular digraph on $n\geq n_0$ vertices with $d \ge \alpha n $ can be covered by at most $n/(d+1)$ vertex-disjoint cycles, and moreover that if G is an oriented graph, then at most $n/(2d+1)$ cycles suffice.

Détail

DOI : 10.1017/fms.2025.28

Bibliographie

[1] Abreu, M., Gauci, J.B., Labbate, D., Mazzuoccolo, G., and Zerafa, J. P., ‘Extending perfect matchings to Hamiltonian cycles in line graphs’, Electron. J. Comb. 28(1) (2021), Paper P1.7. Google Scholar

[2] Akiyama, J., Exoo, G., and Harary, F., ‘Covering and packing in graphs IV: Linear arboricity’, Networks 11(1), (2006) 69–72. Google Scholar | DOI

[3] Balogh, J., Mousset, F., and Skokan, J., ‘Stability for vertex cycle covers’, Electron. J. Comb. 24 (2017), Paper P3.56. Google Scholar

[4] Dantzig, G.B. and Fulkerson, D.R., ‘On the Max Flow MinCut Theorem of Networks’, in Linear Inequalities and Related systems, Ann. Math. Studies 38 (1956), 215–221. Google Scholar

[5] Diestel, R., ‘Graph Theory (4th Edition)’, Graduate Texts in Mathematics 173, Springer (2012). Google Scholar

[6] Dilworth, P., ‘A decomposition theorem for partially ordered sets’, Ann. of Math. 51(1), (1950), 161–166. Google Scholar | DOI

[7] Dirac, G.A., ‘Some theorems on abstract graphs’, Proc. Lond. Math. Soc. 2 (1952), 69––81. Google Scholar | DOI

[8] Enomoto, H., Kaneko, A., and Tuza, Z., ‘-factors and covering cycles in graphs of minimum degree ’, Combinatorics (Proc. Coll. Math. Soc. János Bolyai Eger, 1987), North Holland (1988), 213–220. Google Scholar

[9] Feige, U. and Fuchs, E., ‘On the path partition number of -regular graphs’, J Graph Theory 101, 345–378. Google Scholar | DOI

[10] Fink, J., ‘Perfect matchings extend to Hamilton cycles in hypercubes’, J. Combin. Theory. Ser. B 97 (2007) 1074–1076. Google Scholar | DOI

[11] Gallai, T. and Milgram, A.N., ‘Verallgemeinerung eines graphentheoretischen satzes von Redei’, Acta Sci. Math. 21, (1960), 181–186. Google Scholar

[12] Ghouila-Houri, A., ‘Une condition suffisante d’existence d’un circuit hamiltonien’, C.R. Acad. Sci. Paris 25 (1960), 495–497. Google Scholar

[13] Gruslys, V. and Letzter, S., ‘Cycle partitions of regular graphs’, Comb. Probab. Comput. 30(4) (2021), 526–549. Google Scholar | DOI

[14] Häggkvist, R., ‘On -Hamiltonian graphs’, In Graph Theory and Related Topics, Bondy, J.A. and Murty, U.S.R., (Academic Press, New York, 1979), 219–231. Google Scholar

[15] Han, J., ‘On vertex-disjoint paths in regular graphs’, Electron. J. Comb. 25 (2018), Paper P2.12. Google Scholar

[16] Jackson, B., ‘Long paths and cycles in oriented graphs’, J Graph Theory 5 (1981), 245–252. Google Scholar | DOI

[17] Keevash, P., Kühn, D., and Osthus, D., ‘An exact minimum degree condition for Hamilton cycles in oriented graphs’, J. Lond. Math. Soc. 79 (2009), 144–166. Google Scholar | DOI

[18] Kouider, M., ‘Covering vertices by cycles’, J Graph Theory 18 (1994) 757–776. Google Scholar | DOI

[19] Kouider, M. and Lonc, Z., ‘Covering cycles and k-term degree sums’, Combinatorica, 16 (1996), 407–412. Google Scholar | DOI

[20] Kouider, M. and Zamime, M., ‘On the path partition of graphs’, (2022). Google Scholar | arXiv

[21] Kühn, D., Lo, A., Osthus, D., and Staden, K., ‘The robust component structure of dense regular graphs and applications’, Proc. Lond. Math. Soc. 110(1) (2015), 19–56. Google Scholar | DOI

[22] Kühn, D. and Osthus, D., ‘Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments’, Adv. Math. 237 (2013), 62–146. Google Scholar | DOI

[23] Kühn, D., Osthus, D., and Treglown, A., ‘Hamiltonian degree sequences in digraphs’, J. Combin. Theory. Ser. B 100 (2010), 367–380. Google Scholar | DOI

[24] Vergnas, M. Las, ‘Problèmes de couplages et problèmes hamiltoniens en Théorie des graphes’, Ph.D. Thesis, University of Paris, (1972). Google Scholar

[25] Lo, A. and Patel, V., ‘Hamilton cycles in sparse robustly expanding digraphs’, Electron. J. Comb. 25(3) (2018), P3.44 Google Scholar

[26] Lo, A.., Patel, V., Skokan, J., and Talbot, J., ‘Decomposing tournaments into paths’, Proc. Lond. Math. Soc. 121(2) (2020), 426–461. Google Scholar | DOI

[27] Lo, A., Patel, V., and Yıldız, M. A., ‘Hamilton cycles in dense regular digraphs and oriented graphs’, J. Combin. Theory. Ser. B 164 (2024), 119–160. Google Scholar | DOI

[28] Magnant, C. and Martin, D., ‘A note on the path cover number of regular graphs’, Australas. J. Comb. 43 (2009), 211–217. Google Scholar

[29] Magnant, C., Wang, H., and Yuan, S., ‘Path partitions of almost regular graphs’, Australas. J. Comb. 64 (2016), 334–340. Google Scholar

[30] Ore, O., ‘Arc coverings of graphs’, Annali di Matematica Pura ed Applicata 55 (1961), 315–321. Google Scholar | DOI

[31] Reed, B., ‘Paths, stars and the number three’, Comb. Probab. Comput. 3 (1996), 277–295. Google Scholar | DOI

[32] Ruskey, F. and Savage, C. D., ‘Hamilton cycles that extend transposition matchings in Cayley graphs of ’, SIAM J. Discrete Math. 6(1) (1993), 152–166. Google Scholar | DOI

[33] Staden, K., ‘Robust expansion and Hamiltonicity’, PhD Thesis, University of Birmingham (2015). Google Scholar

[34] Vizing, V.G., ‘On an estimate of the chromatic class of a p-graph’, Diskret. Analiz. 3 (1964), 25–30. Google Scholar

[35] Yang, Z., ‘On -Hamiltonian graphs’, Discrete Math. 196 (1999), 281–286. Google Scholar | DOI

[36] Yu, G., ‘Covering 2-connected 3-regular graphs with disjoint paths’ J Graph Theory 88 (2018), 385–401. Google Scholar | DOI