Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T19:19:43.305Z 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: [email protected])
PETER KEEVASH
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK (e-mail: [email protected])
BENNY SUDAKOV
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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