The second neighbourhood for bipartite tournaments
Author(s) -
Ruijuan Li,
Bin Sheng
Publication year - 2017
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2018
Subject(s) - mathematics , bipartite graph , neighbourhood (mathematics) , combinatorics , discrete mathematics , graph , mathematical analysis
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)|.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom