摘要或動機

The project is devoted to the study of the Seymour’s Second Neighborhood conjecture by determining the properties of possible counterexamples to it. This problem has remained unsolved for more than 30 years, although there is some progress in its solution. The vector of the research is aimed at the analysis of possible counterexamples to the conjecture with the subsequent finding of some of their characteristic values. In addition, attention is focused on the generalized Seymour’s conjecture for vertex-weighted graphs. Combinatorial research methods and graph theory methods were used in the project. The author determines the values ​​of densities and diameters of possible counterexamples, considers separately directed graphs of diameter 3. The conditions under which specific graphs cannot be counterexamples to the Seymour’s conjecture with the minimum number or vertices are defined. The relationship between the Seymour’s conjecture and vertex-weighted Seymour’s conjecture is explained. It is proved that if there exists at least one counterexample, then there exist counterexamples with an arbitrary diameter not less than 3. Under the same condition, the existence of counterexamples with a density both close to 0 and close to 1 is also proved. The equivalence of the above two conjectures is substantiated in detail. It can be concluded that if the Seymour’s Second Neighborhood Conjecture is true for a directed graph of diameter 3, then it is true for any digraph, so that problem will be solved. Moreover, if the conjecture is true, then vertex-weighted version of this conjecture is true too. That is why a digraph of diameter 3 needs further research.