# zbMATH — the first resource for mathematics

Second neighborhood via first neighborhood in digraphs. (English) Zbl 1017.05057
Summary: Let $$D$$ be a simple digraph without loops or digons. For any $$v\in V(D)$$, the first out-neighborhood $$N^+(v)$$ is the set of all vertices with out-distance 1 from $$v$$ and the second neighborhood $$N^{++}(v)$$ of $$v$$ is the set of all vertices with out-distance 2 from $$v$$. We show that every simple digraph without loops or digons contains a vertex $$v$$ such that $$|N^{++}(v)|\geq \gamma|N^+(v)|$$, where $$\gamma = 0.657298\cdots$$ is the unique real root of the equation $$2x^3+x^2-1=0$$.

##### MSC:
 05C38 Paths and cycles 05C20 Directed graphs (digraphs), tournaments
##### Keywords:
digraph; cycle; in-degree; out-degree; neighborhood
Full Text: