The Second Neighbourhood for Bipartite Tournaments
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2019-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2018 |
| _version_ | 1827844581744443392 |
|---|---|
| author | Li Ruijuan Sheng Bin |
| author_facet | Li Ruijuan Sheng Bin |
| author_sort | Li Ruijuan |
| collection | DOAJ |
| description | 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)|. |
| first_indexed | 2024-03-12T08:44:56Z |
| format | Article |
| id | doaj.art-7d0205a81a03413ebac88031ee999098 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:56Z |
| publishDate | 2019-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-7d0205a81a03413ebac88031ee9990982023-09-02T16:30:00ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922019-05-0139255556510.7151/dmgt.2018dmgt.2018The Second Neighbourhood for Bipartite TournamentsLi Ruijuan0Sheng Bin1School of Mathematical Sciences, Shanxi University, Taiyuan030006, PR ChinaCollege of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics,Nanjing211106, PR ChinaLet 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)|.https://doi.org/10.7151/dmgt.2018second out-neighbourhoodout-neighbourhoodin-neighbourhoodbipartite tournament05c2005c1205c07 |
| spellingShingle | Li Ruijuan Sheng Bin The Second Neighbourhood for Bipartite Tournaments Discussiones Mathematicae Graph Theory second out-neighbourhood out-neighbourhood in-neighbourhood bipartite tournament 05c20 05c12 05c07 |
| title | The Second Neighbourhood for Bipartite Tournaments |
| title_full | The Second Neighbourhood for Bipartite Tournaments |
| title_fullStr | The Second Neighbourhood for Bipartite Tournaments |
| title_full_unstemmed | The Second Neighbourhood for Bipartite Tournaments |
| title_short | The Second Neighbourhood for Bipartite Tournaments |
| title_sort | second neighbourhood for bipartite tournaments |
| topic | second out-neighbourhood out-neighbourhood in-neighbourhood bipartite tournament 05c20 05c12 05c07 |
| url | https://doi.org/10.7151/dmgt.2018 |
| work_keys_str_mv | AT liruijuan thesecondneighbourhoodforbipartitetournaments AT shengbin thesecondneighbourhoodforbipartitetournaments AT liruijuan secondneighbourhoodforbipartitetournaments AT shengbin secondneighbourhoodforbipartitetournaments |