Cycle Partition of Dense Regular Digraphs and Oriented Graphs

EUROCOMB’23

Allan Lo Viresh Patel Mehmet Akif Yildiz

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-099

PDF
Abstract
Magnant and Martin \cite{PathCover} conjectured that every $d$-regular graph on $n$ vertices can be covered by $n/(d+1)$ vertex-disjoint paths. Gruslys and Letzter \cite{GruslysLetzter} verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all $\alpha>0$, there exists $n_0=n_0(\alpha)$ such that every $d$-regular digraph on $n$ vertices with $d \ge \alpha n $ can be covered by at most $n/(d+1)$ vertex-disjoint cycles. Moreover if $G$ is an oriented graph, then $n/(2d+1)$ cycles suffice. This also establishes Jackson‘s long standing conjecture \cite{JacksonConjecture} for large $n$ that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian.

Pages:
717–724
References

M. Abreu, J. B. Gauci, D. Labbate, G. Mazzuoccolo, and J. P. Zerafa. Extending perfect matchings to Hamiltonian cycles in line graphs. Electron. J. Combin. , 28(1), (2021), Paper P1.7.
https://doi.org/10.37236/9143

J. Akiyama, G. Exoo, and F. Harary. Covering and packing in graphs IV: Linear arboricity. Networks, 11(1), (2006), 69--72.
https://doi.org/10.1002/net.3230110108

J. Balogh, F. Mousset, and J. Skokan. Stability for vertex cycle covers. Electron. J. Combin. 24 (2017), Paper P3.56.
https://doi.org/10.37236/5185

P. Dilworth. A decomposition theorem for partially ordered sets. Ann. of Math. 51(1), (1950), 161--166.
https://doi.org/10.2307/1969503

G.A. Dirac. Some theorems on abstract graphs. Proc. Lond. Math. Soc. 2 (1952), 69--81.
https://doi.org/10.1112/plms/s3-2.1.69

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

U. Feige and E. Fuchs. On the path partition number of 6‐regular graphs. Journal of Graph Theory, 101, 345--378.
https://doi.org/10.1002/jgt.22830

J. Fink. Perfect matchings extend to Hamilton cycles in hypercubes. J. Combin. Theory Ser. B, 97 (2007) 1074--1076.
https://doi.org/10.1016/j.jctb.2007.02.007

T. Gallai and A. N. Milgram. Verallgemeinerung eines graphentheoretischen satzes von Redei. Acta Sci. Math, 21, (1960), 181--186.

A. Ghouila-Houri. Une condition suffisante d'existence d'un circuit hamiltonien. C.R. Acad. Sci. Paris 25 (1960), 495--497.

V. Gruslys and S. Letzter. Cycle partitions of regular graphs. Combin. Probab. Comput., 30(4) (2021), 526--549.
https://doi.org/10.1017/S0963548320000553

R. Häggkvist. On F-Hamiltonian graphs. In Graph Theory and Related Topics by J. A. Bondy, U.S.R. Murty, Academic Press, New York, (1979), 219--231.

J. Han. On vertex-disjoint paths in regular graphs. Electron. J. Combin. 25 (2018), Paper P2.12.
https://doi.org/10.37236/7109

B. Jackson. Long paths and cycles in oriented graphs. J. Graph Theory 5 (1981), 245--252.
https://doi.org/10.1002/jgt.3190050204

P. Keevash, D. Kühn, and D. Osthus. An exact minimum degree condition for Hamilton cycles in oriented graphs. J. Lond. Math. Soc. 79 (2009), 144--166.
https://doi.org/10.1112/jlms/jdn065

M. Kouider. Covering vertices by cycles. J. Graph Theory, 18 (1994) 757--776.
https://doi.org/10.1002/jgt.3190180802

M. Kouider and Z. Lonc. Covering cycles and k-term degree sums. Combinatorica, 16 (1996), 407--412.
https://doi.org/10.1007/BF01261324

D. Kühn, A. Lo, D. Osthus, and K. Staden. The robust component structure of dense regular graphs and applications. Proc. Lond. Math. Soc. 110(1) (2015), 19--56.
https://doi.org/10.1112/plms/pdu039

D. Kühn and D. Osthus. Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments. Adv. Math., 237 (2013), 62--146.
https://doi.org/10.1016/j.aim.2013.01.005

D. Kühn, D. Osthus, and A. Treglown. Hamiltonian degree sequences in digraphs. J. Combin. Theory Ser. B, 100 (2010), 367--380.
https://doi.org/10.1016/j.jctb.2009.11.004

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

A. Lo and V. Patel. Hamilton cycles in sparse robustly expanding digraphs. Electron. J. Comb., 25(3) (2018), P3.44
https://doi.org/10.37236/7418

A. Lo, V. Patel, and M.A. Yıldız. Hamilton cycles in dense regular digraphs and oriented graphs. arXiv: https://arxiv.org/abs/2203.10112 (2022).
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-099

C. Magnant and D. Martin. A note on the path cover number of regular graphs. Australas. J. Combin. 43 (2009), 211--217.

O. Ore. Arc coverings of graphs. Annali di Matematica Pura ed Applicata, 55, (1961), 315--321.
https://doi.org/10.1007/BF02412090

F. Ruskey and C. D. Savage. Hamilton cycles that extend transposition matchings in Cayley graphs of . SIAM Journal on Discrete Mathematics 6(1) (1993) 152--166.
https://doi.org/10.1137/0406012

Z. Yang. On F-Hamiltonian graphs. Discrete Math., 196, (1999), 281-286.
https://doi.org/10.1016/S0012-365X(98)00216-7

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Allan Lo, Viresh Patel, Mehmet Akif Yildiz

PDF