Authors: R. Li , B. Sheng Title: The second neighbourhood for bipartite tournaments Source: Discussiones Mathematicae Graph Theory Received 12.06.2017, Revised 13.10.2017, Accepted 13.10.2017, doi: 10.7151/dmgt.2018 | |
Abstract: 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)|. | |
Keywords: second out-neighbourhood, out-neighbourhood, in-neighbourhood, bipartite tournament | |
Links: |