Abstract
Let G be a digraph (without parallel edges) such that every directed cycle has length at least four; let β(G) denote the size of the smallest subset X ⊆ E(G) such that G\X has no directed cycles, and let γ(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 γ(G) = 0 then β(G) = 0; what can we say about β(G) if γ(G) is bounded? We prove that in general β(G) ≤ γ(G). We conjecture that in fact β(G) ≤ 1/2γ(G) (this would be best possible if true), and prove this conjecture in two special cases: when V(G) is the union of two cliques 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, vw.
Original language | English (US) |
---|---|
Pages (from-to) | 1-18 |
Number of pages | 18 |
Journal | Combinatorica |
Volume | 28 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2008 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics