Cycles in dense digraphs

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

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 languageEnglish (US)
Pages (from-to)1-18
Number of pages18
JournalCombinatorica
Volume28
Issue number1
DOIs
StatePublished - Jan 2008

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Cycles in dense digraphs'. Together they form a unique fingerprint.

Cite this