Кібернетика та комп'ютерні технології (Dec 2020)
About Structure of Graph Obstructions for Klein Surface with 9 Vertices
Abstract
The structure of the 9 vertex obstructive graphs for the nonorientable surface of the genus 2 is established by the method of (-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 phi-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 phi-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 N2 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 N3 and there exists a locally projective-planar subgraph K of the graph H \ u which satisfies the condition: (tK({a,b},N3)=1)and(tK\u({a,b},N2)=2), where tK({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 Ki 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 K5 or K3,3), which covers the set of edges of the graph H.
Keywords
