A-trails of embedded graphs and twisted duals

Qi Yan, Xian'an Jin

Abstract


Kotzig showed that every connected 4-regular plane graph has an A-trail—an Eulerian circuit that turns either left or right at each vertex. However, this statement is not true for Eulerian plane graphs and determining if an Eulerian plane graph has an A-trail is NP-hard. The aim of this paper is to give a characterization of Eulerian embedded graphs having an A-trail. Andersen et al. showed the existence of orthogonal pairs of A-trails in checkerboard colourable 4-regular graphs embedded on the plane, torus and projective plane. A problem posed in their paper is to characterize Eulerian embedded graphs (not necessarily checkerboard colourable) which contain two orthogonal A-trails. In this article, we solve this problem in terms of twisted duals. Several related results are also obtained.


Keywords


Embedded graphs, twisted duals, Eulerian, A-trails, checkerboard colourable

Full Text:

MANUSCRIPT


DOI: https://doi.org/10.26493/1855-3974.2053.c7b

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications