Directed graphs without short cycles

DOI10.1017/S0963548309990460MaRDI QIDQ3557536zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Peter Keevash, Benny Sudakov

Publication date 23 April 2010

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.4690

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Abstract: For a directed graph $G$ without loops or parallel edges, let $$ denote the size of the smallest feedback arc set, i.e., the smallest subset $XsubsetE(G)$ such that $GsmX$ has no directed cycles. Let $gamma(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 $rge4$ satisfies $$, 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 be also used to answer a question of Yuster concerning almost given length cycles in digraphs. We show that for any fixed $0<heta<1/2$ and sufficiently large $n$, if $G$ is a digraph with $n$ vertices and $$, then for any $0lemlehetan-o(n)$ it contains a directed cycle whose length is between $m$ and $m+6het{a}^{-1/2}$. Moreover, there is a constant $C$ such that either $G$ contains directed cycles of every length between $C$ and $hetan-o(n)$ or it is close to a digraph $G^{\prime }$ with a simple structure: every strong component of $G^{\prime }$ is periodic. These results are also tight up to the constant factors.

Recommendations

• Almost given length cycles in digraphs
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• Minimum feedback arc set of \(m\)-free digraphs
• Short cycles in digraphs
• Small feedback vertex sets in planar digraphs

Cites work

• Almost given length cycles in digraphs
• Blow-up lemma
• Cycles in dense digraphs
• scientific article; zbMATH DE number 3483532 (Why is no real title available?)
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• Ranking Tournaments
• Retiming synchronous circuitry
• Testing subgraphs in directed graphs
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments

Cited in

(9)

• Digraphs without directed path of length two or three
• Graphs without spanning closed trails
• Graphs without dead ends
• Minimum feedback arc set of \(m\)-free digraphs
• Almost given length cycles in digraphs
• On the Chudnovsky-Seymour-Sullivan conjecture on cycles in triangle-free digraphs
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• Extremal results on feedback arc sets in digraphs
• Destroying cycles in digraphs

This page was built for publication: Directed graphs without short cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557536)