TY  - JOUR
ID  - Zelenskiy2021
LB  - Zelenskiy2021
AU  - Zelenskiy, Oleksiy
AU  - Darmosiuk, Valentyna
AU  - Nalivayko, Illia
TI  - A note on possible density and diameter of counterexamples to the Seymour's second neighborhood conjecture
ST  - A note on possible density and diameter of counterexamples to the Seymour's second neighborhood conjecture
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2021
VL  - 41
IS  - 4
SP  - 601
EP  - 605
DO  - https://doi.org/10.7494/OpMath.2021.41.4.601
UR  - https://doi.org/10.7494/OpMath.2021.41.4.601
AB  - 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\geq 3\).
KW  - graph theory
KW  - Seymour's second neighborhood conjecture
KW  - density of graph
KW  - diameter of graph
SN  - 1232-9274
ER  -