On the structure of the planar subgraphs of obstruction graphs of a nonorientable surface with a given genus

Fìz.-mat. model. ìnf. tehnol. 2021, 33:105-109

Abstract

The problem of studying the structure of planar graphs with sets of points, which should be critical concerning the distance between cells on the boundaries of which the elements of a given set are located in operations of removing vertices or edges of a graph, is considered. Knowing the structure of these planar graphs, it is possible to construct a finite set of planar graphs with given characteristics required for the construction of obstruction graphs of a given nonorientable genus. The main result is to use the constructed list of plane graphs critical concerning distance 2 to construct obstruction graphs of a given nonorientable genus.

References

1. Khomenko, М. P. (1973). φ - transformation of graphs, preprint IM AHU, Kiev. (in Ukrainian).
2. Khomenko, М. P. (1970). Topological aspects of graph theory, preprint IM AHU, Kiev. (in Russian).
3. Mohar, B., Thomassen, C. (2001). Graphs on Surfaces, Johns Hopkins University Press.
4. Hur, S. (2008). Тhe Кuratowski covering conjecture for graphs of the order less than 10. PhD, Ohio State University.
5. Archdeacon, D., Huneke, P., Kuratowski, A. (1989). Theorem for Nonorientable Surfaces, Journal of combinatorial theory, Series, 46, 173-231.
   DOI https://doi.org/10.1016/0095-8956(89)90043-9