- Tytuł:
- A note on possible density and diameter of countere xamples to the Seymour’s second neighborhood conjecture
- Autorzy:
-
Zelenskiy, Oleksiy
Darmosiuk, Valentyna
Nalivayko, Illia - Powiązania:
- https://bibliotekanauki.pl/articles/2052069.pdf
- Data publikacji:
- 2021
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
graph theory
Seymour’s second neighborhood conjecture
density of graph
diameter of graph - Opis:
- Seymour’s second neighborhood conjecture states that every simple digraph without loops or 2-cycles contains a vertex whose second neighborhood is at least as large as its first. In this paper we show, that from falsity of Seymour’s second neighborhood conjecture it follows that there exist strongly-connected counterexamples with both low and high density (dense and sparse graph). Moreover, we show that if there is a counterexample to conjecture, then it is possible to construct counterexample with any diameter k ≥ 3
- Źródło:
-
Opuscula Mathematica; 2021, 41, 4; 601-605
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł