Directed graphs without short cycles

Details Directed graphs without short cycles Directed graphs without short cycles

2008-09-26

arxiv.org/abs/0809.4690v1

Mathematics

Combinatorics

Scientific paper

For a directed graph $G$ without loops or parallel edges, let $\beta(G)$ denote the size of the smallest feedback arc set, i.e., the smallest subset $X \subset E(G)$ such that $G \sm X$ 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 $r \ge 4$ satisfies $\beta(G) \le c\gamma(G)/r^2$, 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 < \theta < 1/2$ and sufficiently large $n$, if $G$ is a digraph with $n$ vertices and $\beta(G) \ge \theta n^2$, then for any $0 \le m \le \theta n-o(n)$ it contains a directed cycle whose length is between $m$ and $m+6 \theta^{-1/2}$. Moreover, there is a constant $C$ such that either $G$ contains directed cycles of every length between $C$ and $\theta 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.

Affiliated with

Also associated with

No associations

Rating

Directed graphs without short cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Directed graphs without short cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Directed graphs without short cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-713045