## 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. *K*_{4}, *K*_{2,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 *K*_{4}, *K*_{2,3}, *K*_{5}\*е*, *K** _{r}*,

*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