2024, issue 1, p. 47-63
Received 22.02.2024; Revised 08.03.2024; Accepted 19.03.2024
Published 29.03.2024; First Online 31.03.2024
https://doi.org/10.34229/2707-451X.24.1.4
Previous | FULL TEXT (in Ukrainian) | Next
Models of Klein Surface Obstruction Graphs
Volodymyr Petrenjuk 1
* 
, Dmytro Petreniuk 2
1 Central Ukrainian National Technical University, Kropyvnytskyi
2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: petrenjukvi@i.u
The task of researching the structure of graphs of given connectivity, which are obstructions for a given surface of non-oriented kind, and building their models, from which obstruction graphs are formed by removing or compressing a set of edges, is considered. The issue of edge coverage of an obstruction graph of a given kind with a minimum number of quasi-stars with centers – planar graphs that have given sets of points and all edges are significant with respect to the reachability number 2 on the Euclidean plane and has reachability on the projective plane or Klein surface, is considered. K4, K2,3 or a degenerate graph. The task of researching the structure of graphs of undirected kind was considered [4–6]. In [7], the set of minors for the projective plane was compressed to 12 basic minors using the method of relative components, and a set of 62 minors of the Klein surface was constructed. To do this, we considered all non-isomorphic minimal embeddings of each of the basic minors and found the set of all different pairs of vertices that are reachable on the projective plane during the operations of removing or compressing an arbitrary edge of this graph to a point, then a pair of non-adjacent graph vertices was attached to the selected pair of points. In [8], the number of 2-connected obstruction graphs for the Klein surface was calculated, part of the diagrams of these graphs is given in [10]. Note that the following definition of the cell distance is similar to that in [11].Our approach, as a continuation of [9], will consist in finding the edge covering of an obstruction graph of a given kind by the minimum number of subgraphs of the covering from the number of quasi-stars with centers - graphs with essential edges relative to the number of reachability or nonorientable genus during compression to a point or removal operations edges relative to a given set of points with reachability number 2 relative to the Euclidean plane and reachable on projective planes or Klein surfaces, for example, these are subsets of the set of points of graphs K4, K2,3, K5\е, Kr, r ³ 2, or graph-obstructions of the projective plane. We also found the necessary conditions for constructing obstruction graphs for the Klein surface by identifying pairs of center points and hanging vertices of three quasi-stars, thus we have the basis of an algorithm for constructing a larger number of obstruction graphs for the Klein surface. Hypothetically, a graph-obstruction of a given nonorientable genus has the form of a cylindrical surface with n, n ³ 2, disks-bases and a side part, which can have common sets of points on the boundaries and on which are embedded, at least in part, the graph-centers of quasi-stars having a given set of reachability points 2 on the Euclidean plane, and on the side surface there are hanging edges that intersect on the plane and are inserted without crossing with the help of Möbius strips glued to the side surface. At the same time, the edges will have at least two nesting options in the side part of the cylindrical surface, but no more than the number of glued Möbius strips, thanks to which each hanging edge will nest on the Möbius strip, either with only one edge or with two adjacent edges. We have found the necessary conditions for constructing models of obstruction graphs for the Klein surface by identifying pairs of centers and hanging vertices of three quasi-stars, thus we have the basis of an algorithm for constructing a larger number of obstruction graphs for the Klein surface.
The main result: statements 1, 2, 3 and the algorithm for constructing models of 3-connected graph-obstructions of the Klein surface.
Keywords: φ-transformation of graphs, nonorientable surface, prototypes of graph-obstruction.
Cite as: Petrenjuk V., Petreniuk D. Models of Klein Surface Obstruction Graphs. Cybernetics and Computer Technologies. 2024. 1. P. 47–63. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.1.4
References
1. Khomenko М. P. j-transformations of graphs. Preprint IM АSU. Кyjv, 1973. 383 p. (in Russian)
2. Khomenko M.P. Topological aspects of graph theory. Preprint IM АSU, Кyjv, 1970. 299 p. (in Russian)
3. Mohar B., Thomassen C. Graphs on Surfaces. Johns Hopkins University Press, 2001. 412 p. https://doi.org/10.56021/9780801866890
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. Petrenjuk V.І. On the structure of planar subgraphs of obstruction graphs of an unoriented surface of a given kind. Physico-mathematical modeling and information technologies. 2021. № 33. pp. 105–109. https://doi.org/10.15407/fmmit2021.33.105 (in Ukrainian)
7. Flȍtotto A. Embeddability of graphs into the Klein surface. Dissertation, University Bielefeld. 2010. 174 p.
8. Skoda P. Obstructions for embedding graphs into surfaces, Simon Frazer University, PhD dissertation. 2012. 133 р.
9. Petrenjuk V.I., Petreniuk D.A., Oryshaka O.V. The structure of projective planar subgraphs obstruction graphs of a given surface. Cybernetics and computer technologies. 2022. No. 2. P. 1–20. https://doi.org/10.34229/2707-451X.22.2 (in Ukrainian)
10. Petrenjuk V.I., D.A. Petreniuk On the algorithm for constructing 2-connected minors of the Klein surface. Physico-mathematical modeling and information technologies. 2023. No. 37. P. 72–74. https://doi.org/10.15407/fmmit2023.37.072 (in Ukrainian)
11. Van Dam E.R., Koolen J.H., Tanaka H. Distance-regular graphs, E-JC, DS22: Apr 15. 2016. https://doi.org/10.37236/4925
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next