2022, issue 2, p. 13-30
Received 14.07.2022; Revised 28.09.2022; Accepted 29.09.2022
Published 30.09.2022; First Online 05.10.2022
https://doi.org/10.34229/2707-451X.22.2.2
Previous | FULL TEXT (in Ukrainian) | Next
Structure of Projective Planar Subgraphs of the Graph Obstructions for Fixed Surface
Volodymyr Petrenjuk 1 * 
, Dmytro Petreniuk 2, Oleh Oryshaka
1
1 Central Ukrainian National Technical University
2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
* Correspondence: petrenjukvi@i.u
Consider the problem of studying the metric properties of a subgraph G \ v, where v is an arbitrary vertex of obstruction graphs G of a nonorientable genus, which will determine the sets of points of attachment of one subgraph to another and allow constructing prototypes of graphs-obstruction with number of vertices greater than 10 nonorientable genus greater than 1. This problem is related to Erdosh's hypothesis [3] on the coverage of obstruction graphs of an undirected surface of the genus k, where k> 0, the smallest inclusion of the set of k + 1st graph of the homeomorphic K5, or K3,3, in [4] constructively proved for 35 minors of obstruction graphs of the projective plane, a set of 62 with no more than 10 vertices of obstruction graphs and their splits for the Klein surface, as well as some obstruction graphs for other surfaces. In [5], the existence of a finite set of obstruction graphs for a non-orienting surface was proved. A similar problem was considered in [6], where models or prototypes of obstruction graphs were considered. The prototype of the graph-obstruction of the undirected genus, we will call the graphs that have their own subgraph graph-obstruction of the undirected genus. In [7, 8] the tangent problem of covering the set of vertices with the smallest number of cycles-boundaries of 2-cells was considered, the concept of cell distance is given in [9, 10], where the boundaries of an oriented genus of graphs formed from planar graphs and a simple star glued to some of its peaks. Hypothetically, it is possible to obtain them by recursive φ-transformation of the graph-obstruction of the projective plane and a copy of its planar subgraph given on vertices, edges or parts of edges, or simple chains, i.e. achievable parts of the so-called graph-basis (graph of homeomorphic graph Kuratovsky plane). We assume that instead of one subgraph there can be several copies of subgraphs of graphs-obstructions of the projective plane.The article has an introduction and two parts, in which the structural properties of subgraphs of obstruction graphs for an undirected surface, presented as a φ-image of one of the Kuratovsky graphs and at least one planar graph, are investigated. The metric properties of the minimal embeddings of the subgraphs of the obstruction graphs for undirected surfaces are considered, and the main result is Theorems 1, 2, and Lemma 3 as the basis of the prototype construction algorithm.
Keywords: φ-transformation of graphs, nonorientable surface, prototypes of graph-obstruction.
Cite as: Petrenjuk V., Petreniuk D., Oryshaka O. Structure of Projective Planar Subgraphs of the Graph Obstructions for Fixed Surface. Cybernetics and Computer Technologies. 2022. 2. P. 13–30. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.2.2
References
1. Khomenko M.P. Phi-transformation of graphs. Pгерrint IM AHU, Kiev. 1973. 383 p.
2. Khomenko M.P. Topological aspekts of graph theory. Pгерrint IM AHU, Kiev. 1970. 299 c.
3. Mohar B., Thomassen C. Graphs on Surfaces. Johns Hopkins University Press, 2001. 412 p. https://www.sfu.ca/~mohar/Book.html
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. Petrenyuk V.I. On the structure of the planar subgraphs of obstruction graphs of a nonorientable surface with a given genus. Physico-mathematical modeling and informational technologies. 2021. 33. P. 105–109. https://doi.org/10.15407/fmmit2021.33.105
7. Bienstock D., Dean N. On obstructions to small face covers in planar graphs, J. Combin. Theory. Ser. B. 1992. 55. P. 163–189. https://doi.org/10.1016/0095-8956%2892%2990040-5
8. Bienstock D., Monma C.L. On the complexity of covering vertices by faces in a planar graph. SIAM J. Comput. 1988. 17. P. 53–76. https://doi.org/10.1137/0217004
9. Mohar B. Face Covers and the Genus Problem for Apex Graphs. Journal of Combinatorial Theory. Series B. 2001. 82. P. 102–117. https://doi.org/10.1006/jctb.2000.2026
10. Mohar B. Apex graphs with embeddings of face-width three. Discrete Mathematics. 1997. 176. P. 203–210. https://doi.org/10.1016/S0012-365X(96)00363-9
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next