Про алгоритм побудови 2-зв’язних мінорів поверхні  Клейна

Volodymyr Petrenjuk; Dmytro Petrenjuk

doi:10.15407/10.15407/fmmit2023.37.072

Volodymyr Petrenjuk к. фіз.-мат. н., доцент, Центральноукраїнський нац. техн. ун.-т, 25006, Україна, Кропивницький, пр-т. Університетський, 8
Dmytro Petrenjuk к. фіз.-мат. н., ІК ім. Глушкова В.М. НАН України, 03187, Україна, Київ, пр-т акад. Глушкова, 40

DOI: https://doi.org/10.15407/10.15407/fmmit2023.37.072

Ключові слова: граф-обструкція, поверхня Клейна, мінор, 2-зв’зність

Анотація

У роботі розглянута задача побудови діаграм 2-зв’язних мінорів поверхні Клейна, тобто графів неорієнтованого роду 3 – мінімальних відносно роду при операціях стисканні чи видаленні довільного його ребра. Основний результат – лінійний алгоритм, який коректно вирішує цю задачу.

Посилання

Khomenko M.P. (1973). Topological aspects of graph theory. Kyiv: Preprint of the IM AHU. [in Ukrainian].

Khomenko M. P. (1970). -the transformation of graphs. Kyiv: Preprint of the IM AHU. [in Ukrainian].

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

P. Skoda. (2012). Obstructions for embedding graphs into surfaces, Simon Frazer University, Ph.D. dissertation.

Petrenjuk V.I. (2021). On the structure of planar subgraphs of obstruction graphs of the nonorientable surface of a given genus. Physical-mathematical modeling and information technologies, 33, 105–109. Retrieved from: https://doi.org/10.15407/fmmit2021.33.105. [in Ukrainian].

Anna Flototto. (2010). Embeddability of graphs into the Klein surface. University Bielefeld. Ph.D. dissertation.

Hur Sur J. (2008). The Kuratowski covering conjecture for graphs of the order less than 10. Ohio State University, Ph.D. dissertation. Retrieved from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1209141894.

Petrenyuk V.I., Petrenyuk D.A., Orishaka O.V. (2022), The structure of projective planar subgraphs of graphs - obstructions of a given surface. Cybernetics and computer technologies, 2, 13-30. Retrieved from: http://cctech.org.ua/images/docs/Articles/2022/paper_22_2_2.pdf. [in Ukrainian].