Одержано 02.07.2020; Виправлено 25.11.2020; Прийнято 17.12.2020

Надруковано 31.12.2020; Вперше Online 22.01.2021

https://doi.org/10.34229/2707-451X.20.4.5

Попередня  |  Повний текст  |  Наступна

УДК 519.85

Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна

В.I. Петренюк ^{1 *},   Д.А. Петренюк ²

¹ Центральноукраїнський національний технічний університет, Кропивницький

² Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: petrenjukvi@i.u

Розглянуто задачу встановлення методом j-пеpетвоpення гpафiв структурні властивості 9-ти вершинних графів-обструкцій для поверхні неорієнтованого роду 2. Стаття має вступ та 5 розділів. Вступ містить основні визначення, що проілюстровані, до певної міри, в розділі 1, де наведені кілька твердження про їх властивості. В розділах 2 – 4 досліджено структурні властивості 9-ти вершинних графів-обструкцій для неорієнтованої поверхні шляхом подання як j-образу кількох графів, гомеоморфних одному із графів Куратовського та принаймні одного площинного чи проективно-площинного графа. В розділі 5 міститься новий варіант доведення твердження про особливості мінімальних вкладень скінчених графів в неорієнтовні поверхні, а саме, що, на відміну від орієнтованих поверхонь, границі кліток не містять повторних ребер. Також в розділі 5 наведено інші властивості характерні для вкладень графів до неорієнтованих поверхонь і основний результат. Основний результат: Теорема 1. Кожен граф-обструкція H для N₂–неорієнтованої поверхні роду 2 задовольняє відношенням: 

1. Довільне ребро u, u = (a, b) розміщується на стрічці Мебіуса деяким мінімальним вкладенням графа H в N₃ та існує локально проективно-площинний підграф K графа H \ u, який задовольняє умові: (t_K({a,b}, N₃)=1)˄(t_K\u({a,b}, N₂)=2), де  t_K({a,b}, N) число досяжності множини {a, b} на поверхні N.

2. Існує найменша по включенню множина різних підграфів K_i 2-зв’язного графа H, гомеоморфних K+e, де K – локально площинний підграф графа H \ e із доданим ребром e (принаймні K+e гомеоморфний K₅ чи K_3,3), що покриває множину ребер графа H.

Ключові слова: граф, поверхня Клейна, структурні властивості графа, графи-обструкції, неорієнтована поверхня, стрічка Мебіуса.

Цитувати так: Петренюк В.I., Петренюк Д.А. Про структуру 9-ти вершинних графів-обструкцій для поверхні Клейна. Cybernetics and Computer Technologies. 2020. 4. С. 65–86. https://doi.org/10.34229/2707-451X.20.4.5

Список літератури

           1.     Хоменко М.П. j-пеpетвоpення гpафiв. Пpепp. ИМ АHУ. Киев, 1973. 383 с.

           2.     Хоменко М. П. Топологические аспекты теории графов. Пpепp. ИМ АHУ. Киев, 1970. 299 c.

           3.     Петpенюк В.I., Петpенюк Д.А., Шулінок І.С. Нова верхня межа орієнтованого роду склейки простих графів. Теорія оптимальних рішень. 2018. С. 69–79. http://dspace.nbuv.gov.ua/handle/123456789/144974

           4.     Cashy J. Irreducible graphs for the Klein bottle. Ph.D. Thesis, Ohio State University, 2000.

           5.     Mohar B., Thomassen C. Graphs on Surfaces. Johns Hopkins University Press, 2001.

           6.     Hur S. Тhe Кuratowski covering conjecture for graphs of order less than 10. Phd, Ohio State University, 2008. https://etd.ohiolink.edu/rws_etd/send_file/send?accession=osu1209141894&disposition=inline

           7.     Петренюк В.І., Петренюк Д.А. Нова верхня межа неорієнтованого роду простого графа. Комп’ютерна математика. 2019. 1. С. 10–19. http://dspace.nbuv.gov.ua/handle/123456789/161928

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна