Seymour's Verteces-Weighted Conjecture
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 sa...
Saved in:
| Date: | 2022 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2022
|
| Online Access: | http://mcm-math.kpnu.edu.ua/article/view/274036 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Institution
Mathematical and computer modelling. Series: Physical and mathematical sciences| _version_ | 1856543264613597184 |
|---|---|
| author | Динич, Альона Зеленський, Олексій Дармосюк, Валентина |
| author_facet | Динич, Альона Зеленський, Олексій Дармосюк, Валентина |
| author_sort | Динич, Альона |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2023-02-16T12:51:48Z |
| description | 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. |
| first_indexed | 2025-07-17T10:43:47Z |
| format | Article |
| id | mcm-mathkpnueduua-article-274036 |
| institution | Mathematical and computer modelling. Series: Physical and mathematical sciences |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:43:47Z |
| publishDate | 2022 |
| publisher | Кам'янець-Подільський національний університет імені Івана Огієнка |
| record_format | ojs |
| spelling | mcm-mathkpnueduua-article-2740362023-02-16T12:51:48Z Seymour's Verteces-Weighted Conjecture Вершинно-зважена гіпотеза Сеймура Динич, Альона Зеленський, Олексій Дармосюк, Валентина 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. Гіпотеза Сеймура – одна з найвідоміших у теорії графів невирішених математичних проблем, яку сформулював Пол Сеймур у 1990 році. Ця проблема також відома під назвою «задача другої околиці». Орієнтований граф моделює соціальну мережу, у якій жодні дві людини одночасно не знають один одного. Ця гіпотеза стверджує, що знайдеться хоча б одна людина, для якої знайомих знайомих буде не менше, ніж знайомих. Означення та базові теореми теорії графів описані в [1-3]. Для довільного графа гіпотеза Сеймура залишається невирішеною, проте вже існують доведення для часткових випадків та для деяких видів графів, які наведені у [4-6]. Seacrest Tyler [5] дослідив гіпотезу Сеймура для графів зі зваженими дугами, В [6] доведено, що кожен орієнтований граф без петель та циклів довжини два містить вершину v, для якої другий окіл більше або рівне за перший помножений на певну константу. В [7] наведено достатні умови, за яких може існувати вершина Сеймура v Î V(D), а також розглянуто властивості мінімального графа, який не має такої вершини. Доведено, що якщо існує один такий граф, то існує нескінченна кількість сильно зв’язних графів, які не мають такої вершини. Актуальність обраної теми дослідження визначається стрімкими темпами розвитку сучасної теорії графів, які пов’язані із розширенням її сфери використання: бізнес, логістика, туризм і, головне, моделювання різних мереж. Одним із продовжень гіпотези є розгляд вершинно-зважених орієнтованих графів. У цій статті ми представили версію гіпотези для вершинно-зважених орієнтованих графів і довели, що гіпотеза Сеймура еквівалентна гіпотезі для вершинно-зважених орієнтованих графів. Кам'янець-Подільський національний університет імені Івана Огієнка 2022-10-27 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/274036 10.32626/2308-5878.2022-23.44-48 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2022: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 23; 44-48 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2022: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 23; 44-48 2308-5878 10.32626/2308-5878.2022-23 uk http://mcm-math.kpnu.edu.ua/article/view/274036/269268 |
| spellingShingle | Динич, Альона Зеленський, Олексій Дармосюк, Валентина Seymour's Verteces-Weighted Conjecture |
| title | Seymour's Verteces-Weighted Conjecture |
| title_alt | Вершинно-зважена гіпотеза Сеймура |
| title_full | Seymour's Verteces-Weighted Conjecture |
| title_fullStr | Seymour's Verteces-Weighted Conjecture |
| title_full_unstemmed | Seymour's Verteces-Weighted Conjecture |
| title_short | Seymour's Verteces-Weighted Conjecture |
| title_sort | seymour's verteces-weighted conjecture |
| url | http://mcm-math.kpnu.edu.ua/article/view/274036 |
| work_keys_str_mv | AT diničalʹona seymoursvertecesweightedconjecture AT zelensʹkijoleksíj seymoursvertecesweightedconjecture AT darmosûkvalentina seymoursvertecesweightedconjecture AT diničalʹona veršinnozvaženagípotezasejmura AT zelensʹkijoleksíj veršinnozvaženagípotezasejmura AT darmosûkvalentina veršinnozvaženagípotezasejmura |