Cycles in dense digraphs

Details Cycles in dense digraphs Cycles in dense digraphs

2007-02-06

arxiv.org/abs/math/0702147v1

Mathematics

Combinatorics

Scientific paper

Let G be a digraph (without parallel edges) such that every directed cycle has length at least four; let $\beta(G)$ denote the size of the smallest subset X in E(G) such that $G\X$ has no directed cycles, and let $\gamma(G)$ be the number of unordered pairs {u,v} of vertices such that u,v are nonadjacent in G. It is easy to see that if $\gamma(G) = 0$ then $\beta(G) = 0$; what can we say about $\beta(G)$ if $\gamma(G)$ is bounded? We prove that in general $\beta(G)$ is at most $\gamma(G)$. We conjecture that in fact $\beta(G)$ is at most $\gamma(G)/2$ (this would be best possible if true), and prove this conjecture in two special cases: 1. when V(G) is the union of two cliques, 2. when the vertices of G can be arranged in a circle such that if distinct u,v,w are in clockwise order and uw is a (directed) edge, then so are both uv and vw.

Affiliated with

Also associated with

No associations

Rating

Cycles in dense digraphs 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 Cycles in dense digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cycles in dense digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427411