Hostname: page-component-745bb68f8f-cphqk Total loading time: 0 Render date: 2025-02-06T23:11:24.349Z Has data issue: false hasContentIssue false
  • English
  • Français

Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs

Published online by Cambridge University Press:  12 September 2013

HAO HUANG ,
JIE MA ,
ASAF SHAPIRA ,
BENNY SUDAKOV  and
RAPHAEL YUSTER
HAO HUANG
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: huanghao@math.ucla.edu)
JIE MA
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: jiema@math.ucla.edu)
ASAF SHAPIRA
Affiliation:
School of Mathematics, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: asafico@tau.ac.il)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, 8092 Zurich, Switzerland and Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: bsudakov@math.ucla.edu)
RAPHAEL YUSTER
Affiliation:
Department of Mathematics, University of Haifa, Haifa 31905, Israel (e-mail: raphy@math.haifa.ac.il)
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.

A minimum feedback arc set of a directed graph G is a smallest set of arcs whose removal makes G acyclic. Its cardinality is denoted by β(G). We show that a simple Eulerian digraph with n vertices and m arcs has β(G) ≥ m2/2n2+m/2n, and this bound is optimal for infinitely many m, n. Using this result we prove that a simple Eulerian digraph contains a cycle of length at most 6n2/m, and has an Eulerian subgraph with minimum degree at least m2/24n3. Both estimates are tight up to a constant factor. Finally, motivated by a conjecture of Bollobás and Scott, we also show how to find long cycles in Eulerian digraphs.

Keywords

Primary 05C20Secondary 05C38
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 6 , November 2013 , pp. 859 - 873
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Alon, N. (2006) Ranking tournaments. SIAM J. Discrete Math. 20 137–142.Google Scholar
[2]Bollobás, B. (1998) Modern Graph Theory, Vol. 184 of Graduate Texts in Mathematics, Springer.Google Scholar
[3]Bollobás, B. and Scott, A. (1996) A proof of a conjecture of Bondy concerning paths in weighted digraphs. J. Combin. Theory Ser. B 66 283–292.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.Google Scholar
[6]Chudnovsky, M., Seymour, P. and Sullivan, B. (2008) Cycles in dense digraphs. Combinatorica 28 1–18.CrossRefGoogle Scholar
[7]Fox, J., Keevash, P. and Sudakov, B. (2010) Directed graphs without short cycles. Combin. Probab. Comput. 19 285–301.Google Scholar
[8]Leiserson, C. and Saxe, J. (1991) Retiming synchronous circuitry. Algorithmica 6 5–35.Google Scholar
[9]Nathanson, M. The Caccetta–Häggkvist conjecture and additive number theory. www.aimath.org/preprints.htmlGoogle Scholar
[10]Shaw, A. (1974) The Logical Design of Operating Systems, Prentice Hall.Google Scholar
[11]Sullivan, B. (2008) Extremal problems in digraphs. PhD thesis, Princeton University.Google Scholar
[12]Sullivan, B. A summary of results and problems related to the Caccetta–Häggkvist conjecture. http://arxiv.org/abs/math/0605646v1Google Scholar