Вершинно-зважена гіпотеза Сеймура
DOI:
https://doi.org/10.32626/2308-5878.2022-23.44-48Анотація
Гіпотеза Сеймура – одна з найвідоміших у теорії графів невирішених математичних проблем, яку сформулював Пол Сеймур у 1990 році. Ця проблема також відома під назвою «задача другої околиці».
Орієнтований граф моделює соціальну мережу, у якій жодні дві людини одночасно не знають один одного. Ця гіпотеза стверджує, що знайдеться хоча б одна людина, для якої знайомих знайомих буде не менше, ніж знайомих.
Означення та базові теореми теорії графів описані в [1-3]. Для довільного графа гіпотеза Сеймура залишається невирішеною, проте вже існують доведення для часткових випадків та для деяких видів графів, які наведені у [4-6].
Seacrest Tyler [5] дослідив гіпотезу Сеймура для графів зі зваженими дугами,
В [6] доведено, що кожен орієнтований граф без петель та циклів довжини два містить вершину v, для якої другий окіл більше або рівне за перший помножений на певну константу.
В [7] наведено достатні умови, за яких може існувати вершина Сеймура v Î V(D), а також розглянуто властивості мінімального графа, який не має такої вершини. Доведено, що якщо існує один такий граф, то існує нескінченна кількість сильно зв’язних графів, які не мають такої вершини.
Актуальність обраної теми дослідження визначається стрімкими темпами розвитку сучасної теорії графів, які пов’язані із розширенням її сфери використання: бізнес, логістика, туризм і, головне, моделювання різних мереж.
Одним із продовжень гіпотези є розгляд вершинно-зважених орієнтованих графів. У цій статті ми представили версію гіпотези для вершинно-зважених орієнтованих графів і довели, що гіпотеза Сеймура еквівалентна гіпотезі для вершинно-зважених орієнтованих графів.
Посилання
Карнаух Т. О., Ставровський А. Б. Теорія графів у задачах. Київ: ВПЦ «Київський університет», 2004. 90 c.
Дяченко М. П. Методичні рекомендації щодо забезпечення самостійної роботи з дисципліни «Дискретні структури». Київ: МАУП, 2018. 77 с.
Diestel R. Graph Theory. Graduate Texts in Mathematics. 2000. Vol. 173. P. 7.
Fisher D. C. Squaring a tournament: a proof of Dean's conjecture. J. Graph Theory. 1996. Vol. 23. №1. P. 43-48.
Seacrest T. The Arc-Weighted Version of the Second Neighborhood Conjecture. Journal of Graph Theory. 2015. Vol. 78 (3). P. 219-228.
Chen G., Shen J., Yuster R. Second neighborhood via first neighborhood in digraphs. Ann. Comb. 2003. Vol. 7. Issue 1. P. 15-20.
Brantner J., Brockman G., Kay B., Snively E. Contributions to Seymour’s second neighborhood conjecture. Involve. 2009. Vol. 2. №4. P. 390.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).