Genus ranges of 4-regular rigid vertex graphs (Q888603)

Summary: 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 \(2n\) vertices (\(n>1\)), we prove that all intervals \([a, b]\) for all \(a<b \leq n\), and singletons \([h, h]\) for some \(h\leq n\), are realized as genus ranges. For graphs with \(2n-1\) vertices (\(n\geq 1\)), we prove that all intervals \([a, b]\) for all \(a<b \leq n\) except \([0,n]\), and \([h,h]\) for some \(h\leq n\), are realized as genus ranges. We also provide constructions of graphs that realize these ranges.