Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-07T09:25:58.875Z Has data issue: false hasContentIssue false
  • English
  • Français

Directed Graphs Without Short Cycles

Published online by Cambridge University Press:  01 October 2009

JACOB FOX ,
PETER KEEVASH  and
BENNY SUDAKOV
JACOB FOX
Affiliation:
Department of Mathematics, Princeton, NJ 08544, USA (e-mail: jacobfox@math.princeton.edu)
PETER KEEVASH
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: p.keevash@qmul.ac.uk)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: bsudakov@math.ucla.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For a directed graph G without loops or parallel edges, let β(G) denote the size of the smallest feedback arc set, i.e., the smallest subset X ⊂ E(G) such that G ∖ X has no directed cycles. Let γ(G) be the number of unordered pairs of vertices of G which are not adjacent. We prove that every directed graph whose shortest directed cycle has length at least r ≥ 4 satisfies β(G) ≤ cγ(G)/r2, where c is an absolute constant. This is tight up to the constant factor and extends a result of Chudnovsky, Seymour and Sullivan.

This result can also be used to answer a question of Yuster concerning almost given length cycles in digraphs. We show that for any fixed 0 < θ < 1/2 and sufficiently large n, if G is a digraph with n vertices and β(G) ≥ θn2, then for any 0 ≤ m ≤ θn − o(n) it contains a directed cycle whose length is between m and m + 6θ−1/2. Moreover, there is a constant C such that either G contains directed cycles of every length between C and θn − o(n) or it is close to a digraph G′ with a simple structure: every strong component of G′ is periodic. These results are also tight up to the constant factors.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 2 , March 2010 , pp. 285 - 301
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alon, N. (2006) Ranking tournaments. SIAM J. Discrete Math. 20 137–142.CrossRefGoogle Scholar
[2]Alon, N. and Shapira, A. (2004) Testing subgraphs in directed graphs. J. Comput. System Sci. 69 354–382.CrossRefGoogle Scholar
[3]Bang-Jensen, J. and Gutin, G. (2001) Digraphs: Theory, Algorithms and Applications, Springer.Google Scholar
[4]Caccetta, L. and Häggkvist, R. (1978) On minimal digraphs with given girth. In Proc. 9th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton 1978), Congress. Numer. XXI 181–187.Google Scholar
[5]Charbit, P., Thomassé, S. and Yeo, A. (2007) The minimum feedback arc set problem is NP-hard for tournaments. Combin. Probab. Comput. 16 1–4.CrossRefGoogle Scholar
[6]Christofides, D., Keevash, P., Kühn, D. and Osthus, D. Finding Hamilton cycles in robustly expanding digraphs. Submitted.Google Scholar
[7]Chudnovsky, M., Seymour, P. and Sullivan, B. (2008) Cycles in dense digraphs. Combinatorica 28 1–18.CrossRefGoogle Scholar
[8]Komlós, J., Sárközy, G. N. and Szemerédi, E. (1997) Blow-up lemma. Combinatorica 17 109–123.CrossRefGoogle Scholar
[9]Komlós, J. and Simonovits, M. (1996) Szemerédi's regularity lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty, Vol. 2 (Miklós, D., Sós, V. T. and Szőnyi, T., eds), Vol. 2 of Bolyai Society Mathematical Studies, Budapest, pp. 295–352.Google Scholar
[10]Leiserson, C. E. and Saxe, J. B. (1991) Retiming synchronous circuitry. Algorithmica 6 5–35.CrossRefGoogle Scholar
[11]Nathanson, M. B. The Caccetta–Häggkvist conjecture and additive number theory. AIM Preprint 2006-10: www.aimath.org/preprints.html.Google Scholar
[12]Shaw, A. C. (1974) The Logical Design of Operating Systems, Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
[13]Sullivan, B. (2008) Extremal problems in digraphs. PhD thesis, Princeton University.Google Scholar
[14]Sullivan, B. A summary of results and problems related to the Caccetta–Häggkvist conjecture. AIM Preprint 2006-13: www.aimath.org/preprints.html.Google Scholar
[15]Yuster, R. (2008) Almost given length cycles in digraphs. Graphs Combin. 24 59–65.CrossRefGoogle Scholar