## 2020, issue 4, p. 65-86

*Received **02.07.2020;
Revised 25.11.2020; Accepted 17.12.2020*

*Published **31.12.2020;
First Online 22.01.2021*

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

Previous | Full text (in Ukrainian) | Next

**About
Structure of Graph Obstructions for Klein Surface with 9 Vertices**

V.I.
Petrenjuk ^{1 *}, D.A. Petrenjuk ^{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 structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established by the method of j-transformations of the graphs. The problem of establishing the structural properties of 9 vertex obstruction graphs for the surface of the undirected genus 2 by the method of j-transformation of graphs is considered. The article has an introduction and 5 sections. The introduction contains the main definitions, which are illustrated, to some extent, in Section 1, which provides several statements about their properties. Sections 2 – 4 investigate the structural properties of 9 vertex obstruction graphs for an undirected surface by presenting as a j-image of several graphs homeomorphic to one of the Kuratovsky graphs and at least one planar or projective-planar graph. Section 5 contains a new version of the proof of the statement about the peculiarities of the minimal embeddings of finite graphs in nonorientable surfaces, namely, that, in contrast to oriented surfaces, cell boundaries do not contain repeated edges.

Also in section 5 the other properties peculiar to embeddings of graphs to non-oriented surfaces and the main result are given.

The main result is Theorem 1. Each obstruction
graph *H* for a
non-oriented surface *N*_{2} of genus 2
satisfies the following.

1. An arbitrary edge *u*,*u *= (*a*,*b*) is placed on
the Mebius strip by some minimal embedding of the graph *H* in *N _{3}* and there
exists a locally projective-planar subgraph

*K*of the graph

*H*\

*u*which satisfies the condition: (

*t*({

_{K}*a*,

*b*},

*N*

_{3})=1)˄(

*t*({

_{K\u}*a*,

*b*},

*N*

_{2})=2), where

*t*({

_{K}*a*,

*b*},

*N*) is the number of reachability of the set {

*a*,

*b*} on the nonorientable surface

*N*.

2. There exists the smallest inclusion of many
different subgraphs *K _{i}* of a 2-connected graph

*H*homeomorphic to the graph

*K+e*, where

*K*is a locally planar subgraph of the graph

*H*(at least

*K+e*is homemorphic to

*K*

_{5}or

*K*

_{3,3}), which covers the set of edges of the graph

*H*.

**Keywords:** graph, Klein surface,
graph structure, graph obstruction, non-oriented surface, Möbius strip.

**Cite
as: **Petrenjuk
V.I., Petrenjuk D.A. About Structure of Graph Obstructions for Klein Surface
with 9 Vertices. *Cybernetics and Computer Technologies*. 2020. **4**.
P. 65–86. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.4.5

**References**

1. Khomenko M.P. Fi-transformation of graphs. Preprint IM AHU. Kiev, 1973. 383 p. (in Ukranian)

2. Khomenko M.P. Topological aspects of graph theory. Preprint IM ASU. Kiev, 1970. 299 p. (in Russian)

3. Petpenjuk V.I.,
Petpenjuk D.A., Shulenok I.S. A new upper limit of the oriented genus of gluing
simple graphs. *Theory of optimal solutions*. 2018. P. 69–79. (in
Ukranian) 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. Ph.D. Thesis. Ohio State University, 2008. https://etd.ohiolink.edu/rws_etd/send_file/send?accession=osu1209141894&disposition=inline

7. Petrenyuk V.I.,
Petrenyuk D.A. New upper limit of the nonorientable genus of a simple graph. *Computer
Mathematics*. 2019. 1. P. 10–19. (in Ukranian) http://dspace.nbuv.gov.ua/handle/123456789/161928

* *

* *

*ISSN 2707-451X (Online) *

*ISSN 2707-4501 (Print) *

Previous | Full text (in Ukrainian) | Next