z-logo
open-access-imgOpen Access
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)|.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom