Seymour's Verteces-Weighted Conjecture

• Дата: 2022
• Автори: Динич, Альона, Зеленський, Олексій, Дармосюк, Валентина
• Формат: Стаття
• Мова: Ukrainian
• Опубліковано: Кам'янець-Подільський національний університет імені Івана Огієнка 2022
• Онлайн доступ: http://mcm-math.kpnu.edu.ua/article/view/274036
• Назва журналу: Mathematical and computer modelling. Series: Physical and mathematical sciences

Seymour's conjecture is one of the most famous unsolved mathematical problems in graph theory, which was formulated by Paul Seymour in 1990. This problem is also known as the «second neighborhood problem». A directed graph models a social network in which no two people know each other at the same time. This conjecture states that there will be at least one person for whom acquaintances of acquaintances will be no less than acquaintances. Definitions and basic theorems of graph theory are described in [1-3]. For an arbitrary graph, Seymour's hypothesis remains unsolved, but there are already proofs for partial cases and for some types of graphs, which are given in [4-6]. Seacrest Tyler [5] investigated Seymour's conjecture for graphs with weighted arcs. In [6] showed that every simple digraph without loops or digons contains a vertex v for which the second neighborhood is greater than or equal to the first multiplied by a certain constant. In [7] provided sufficient conditions under which there must exist some v Î V(D), as well as examine properties of a minimal graph which does not have such a vertex. We show that if one such graph exists, then there exist infinitely many strongly-connected graphs having no such vertex. The relevance of the chosen research topic is determined by the rapid pace of development of modern graph theory, which is associated with the expansion of its scope of use: business, logistics, tourism and, most importantly, modeling of various networks. One extension of the conjecture is to consider vertex-weighted digraphs. In this paper we introduce a version of the conjecture for vertex-weighted digraphs and proved that the Seymour conjecture is equivalent to conjecture for vertex-weighted digraphs.