20 Jul Properties of possible counterexamples to the Seymour’s Second Neighborhood Conjecture

Seymour’s Second Neighborhood Conjecture states that every simple digraph without loops or two-cycles contains a vertex whose second neighborhood is at least as large as its first. In this project we show that from existence of a counterexample to Second Neighborhood Conjecture it follows that there exist strongly-connected counterexamples with both low and high density (dense and sparse graph). We also show that if there is a counterexample to the conjecture, then it is possible to construct counterexample with any diameter not less than 3. Moreover, we prove that Second Neighborhood Conjecture and Vertex-Weighted Version of Second Neighborhood Conjecture are equivalent.

Category: MATHEMATICS — Country: UKRAINE — Year: 2021

Illia Nalyvaiko

BACK TO PROJECTS