Одержано 14.07.2022; Виправлено 28.09.2022; Прийнято 29.09.2022

Надруковано 30.09.2022; Вперше Online 05.10.2022

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

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.85

Структура проективно площинних підграфів графів-обструкцій заданої поверхні

В.I. Петренюк ^{1 *} ,   Д.А. Петренюк ²,   О.В. Оришака ¹

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

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

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

 

Розглянемо задачу вивчення метричних властивостей підграфів  G\v, де v довільна вершина графа-обструкцій G неорієнтованого роду, які визначатимуть множини точок приєднання одного підграфа до іншого і дозволятиме будувати прототипи графів-обструкцій із числом вершин більшим 10 неорієнтованого роду більшого ніж 1. Певним чином з цією задачею пов’язана гіпотеза Ердьоша [3] про покриття графів-обструкцій неорієнтованої поверхні роду k , де k>0 , найменшою по включенню множиною із  k+1-го графа гомеоморфного K₅, чи K_3,3, в [4] конструктивно доведена для 35-ти мінорів графів-обструкцій проективної площини, множини 62-х із не більшим ніж 10-ма вершинами графів-обструкцій та їхніх розщеплень для поверхні Клейна, а також деяких графів-обструкцій для інших поверхонь. В роботі [5] доведено існування скінченої множини графів-обструкцій для неорієнтовної поверхні. Подібна задача розглядалася в [6], де розглядалися моделі чи прототипи графів-обструкцій. Прототипом графа-обструкції  неорієнтованого роду, будемо називати графи, що мають власним підграфом граф-обструкцію неорієнтованого роду. В роботах [7, 8] розглядалась  дотична задача покриття множини вершин найменшою кількістю циклів-границь 2-кліток, поняття кліткової відстані наведене в [9, 10], де досліджено граничні межі орієнтованого роду графів, утворених з площинних графів і простої зірки, приклеєної до деяких його вершин.  Гіпотетично можливо їх отримати шляхом рекурсивного φ-перетворення графа-обструкції проективної площини та копії його площинного підграфа, заданого на вершинах, ребрах чи частинах ребер, або простих ланцюгах, тобто досяжним частинам так званого графа-основи (графа гомеоморфного графу Куратовського і вкладеного в проективну площину). Вважатимемо, що замість одного підграфа може бути кілька копій підграфів графів-обструкцій проективної площини. Стаття має вступ та дві частини, в яких досліджено структурні властивості підграфів графів-обструкцій для неорієнтованої поверхні, поданих як j-образ одного з графів Куратовського та, принаймні одного, площинного графа. Розглянуто метричні властивості мінімальних вкладень підграфів графів-обструкцій для неорієнтованих поверхонь і основний результат – теореми 1, 2 та лема 3, як основа алгоритму побудови прототипів.

 

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

 

Цитувати так: Петренюк В.I., Петренюк Д.А., Оришака О.В. Структура проективно площинних підграфів графів-обструкцій заданої поверхні. Cybernetics and Computer Technologies. 2022. 2. С. 13–30. https://doi.org/10.34229/2707-451X.22.2.2

 

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

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

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

           3.     Mohar B., Thomassen C. Graphs on Surfaces. Johns Hopkins University Press, 2001. 412 p. https://www.sfu.ca/~mohar/Book.html

           4.     Hur S. Тhe Кuratowski covering conjecture for graphs of order less than 10. Phd, Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1209141894

           5.     Archdeacon D., Huneke P. A Kuratowski Theorem for Nonorientable Surfaces. Journal of combinatorial theory. Series B. 1989. 46. P. 173–231. https://doi.org/10.1016/0095-8956(89)90043-9

           6.     Петренюк В.І. Про структуру площинних підграфів графів-обструкцій неорієнтованої поверхні заданого роду. Фізико математичне моделювання та інформаційні технології. 2021. № 33. C. 105–109. Google Scholar

           7.     Bienstock D., Dean N. On obstructions to small face covers in planar graphs, J. Combin. Theory. Ser. B. 1992. 55. P. 163–189. https://doi.org/10.1016/0095-8956%2892%2990040-5

           8.     Bienstock D., Monma C.L. On the complexity of covering vertices by faces in a planar graph. SIAM J. Comput. 1988. 17. P. 53–76. https://doi.org/10.1137/0217004

           9.     Mohar B. Face Covers and the Genus Problem for Apex Graphs. Journal of Combinatorial Theory. Series B. 2001. 82. P. 102–117. https://doi.org/10.1006/jctb.2000.2026

       10.     Mohar B. Apex graphs with embeddings of face-width three. Discrete Mathematics. 1997. 176. P. 203–210. https://doi.org/10.1016/S0012-365X(96)00363-9

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна