×

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
PDF BibTeX XML Cite
Full Text: DOI