Cyclic Neighborhoods in Digraphs

Thilo Hartel; Dieter Rautenbach

combinatorics

Cyclic Neighborhoods in Digraphs

arXiv:2607.26606

summary

The paper proves that any strongly connected digraph where every vertex’s in‑ or out‑neighbourhood contains a directed cycle must have at least 7n/3 edges, and if the digraph is strongly 2‑connected the bound improves to 8n/3, with both bounds being tight.

Abstract

Let $D$ be a digraph of order $n$ and size $m$ with the property that no out-neighborhood or in-neighborhood of any vertex is acyclic. We show that, if $D$ is strongly connected, then $m \geq 7 n /3$ , and, if $D$ is strongly $2$ -connected, then $m \geq 8 n /3$ . Both results are best-possible.

Topics & keywords

#directed graphs #strong connectivity #cyclic neighborhoods #edge density #extremal graph theorydigraphout-neighborhoodin-neighborhoodstrongly connectedstrongly 2‑connectededge lower bound