Вершинно-зважена гіпотеза Сеймура

Автор(и)

  • Альона Динич Відокремлений структурний підрозділ «Кам'янець-Подільський фаховий коледж» НРЗВО «Кам’янець-Подільський державний інститут» , Україна
  • Олексій Зеленський Кам'янець-Подільський національний університет імені Івана Огієнка, Україна
  • Валентина Дармосюк Миколаївський національний університет імені Сухомлинського, Україна

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##

Опубліковано

2022-10-27