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 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)˄(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: 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