Genus Ranges of 4-Regular Rigid Vertex Graphs.
A rigid vertex of a graph is one that has a prescribed cyclic order of its incident edges. We study orientable genus ranges of 4-regular rigid vertex graphs. The (orientable) genus range is a set of genera values over all orientable surfaces into which a graph is embedded cellularly, and the embeddings of rigid vertex graphs are required to preserve the prescribed cyclic order of incident edges at every vertex. The genus ranges of 4-regular rigid vertex graphs are sets of consecutive integers, and we address two questions: which intervals of integers appear as genus ranges of such graphs, and what types of graphs realize a given genus range. For graphs with 2nvertices (n >1), we prove that all intervals [a, b] for alla < b≤n, and singletons [h, h] for someh≤n, are realized as genus ranges. For graphs with 2n- 1 vertices (n≥ 1), we prove that all intervals [a, b] for alla < b≤nexcept [0, n], and [h, h] for someh≤n, are realized as genus ranges. We also provide constructions of graphs that realize these ranges.
Department of Mathematics, Imperial College London, London, England, UK.
Dorothy
D
Buck
Molecular and Computational Biology Section, University of Southern California, Los Angeles, California, U.S.A.
Egor
E
Dolzhenko
Department of Mathematics and Statistics, University of South Florida, Tampa, Florida, U.S.A.
Nataša
N
Jonoska
Department of Mathematics and Statistics, University of South Florida, Tampa, Florida, U.S.A.
Masahico
M
Saito
European Molecular Biology Laboratory, Heidelberg, Germany.
Karin
K
Valencia
Four-regular rigid vertex graphs; realization of genus ranges; unsigned Gauss codes