R. Li , B. Sheng
The second neighbourhood for bipartite tournaments
Discussiones Mathematicae Graph Theory
Received 12.06.2017, Revised 13.10.2017, Accepted 13.10.2017, doi: 10.7151/dmgt.2018
Let T(X∪ Y, A) be a bipartite tournament with partite sets X, Y and arc set A. For any vertex x∈X∪ Y, the second out-neighbourhood N++(x) of x is the set of all vertices with distance 2 from x. In this paper, we prove that T contains at least two vertices x such that |N++(x)|≥ |N+(x)| unless T is in a special class ℬ1 of bipartite tournaments; show that T contains at least a vertex x such that |N++(x)|≥ |N-(x)| and characterize the class ℬ2 of bipartite tournaments in which there exists exactly one vertex x with this property; and prove that if |X|=|Y| or |X|≥ 4|Y|, then the bipartite tournament T contains a vertex x such that |N++(x)|+|N+(x)|≥ 2|N-(x)|.
second out-neighbourhood, out-neighbourhood, in-neighbourhood, bipartite tournament