Cycles in dense digraphs (Q949775)

From MaRDI portal
Revision as of 18:10, 18 April 2024 by Importer (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Cycles in dense digraphs
scientific article

    Statements

    Cycles in dense digraphs (English)
    0 references
    0 references
    0 references
    0 references
    21 October 2008
    0 references
    \(G\) is a digraph containing no 3-cycles, and \(X\) is a subset of its edges such that \(G \setminus X\) is acyclic. Let \(\beta(G)\) be the minimum cardinality of such an \(X\). The authors wish to bound \(\beta(G)\) with \(\gamma(G)\), that denote the number of unordered pairs \(\{u, v\}\) that are not adjacent in \(G\). Their first result is that \(\beta(G) \leq \gamma(G)\). They also exhibit an infinite family of digraphs for which \(\gamma(G)=2n^2\) for any \(n\) natural, and \(\beta(G)= \gamma(G)/2\). It leads to Conjecture \(\beta(G) \leq \gamma(G)/2\). These inequalities are in intimate relation to the Cacetta-Häggkvist conjecture [\textit{L. Cacetta} and \textit{R. Häggkvist}, in: Proc. 9th southeast. Conf. on Combinatorics, graph theory, and computing, Boca Raton 1978, 181-187 (1978; Zbl 0406.05033)] that asserts: If \(G\) is a digraph containing no 3-cycles, then some vertex has outdegree less than \(n/3\). The conjecture is verified for special graph, namely it holds for {\parindent=6mm \begin{itemize}\item[(i)]if \(V(G)\) is the union of two cliques \item[(ii)]\(G\) is a circular interval digraph. \end{itemize}} The proof techniques involve a four function theorem, that resembles but not equivalent to that of \textit{R. Ahlswede and D. E. Daykin} [Z. Wahrscheinlichkeitstheor. Verw. Geb. 43, 183--185 (1978; Zbl 0357.04011)].
    0 references
    cycles
    0 references
    Cacetta-Häggkvist conjecture
    0 references
    four function theorem
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references