Genus Ranges of 4-Regular Rigid Vertex Graphs

Dorothy Buck, Egor Dolzhenko, Nataša Jonoska, Masahico Saito, Karin Valencia

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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

Original languageEnglish
Article number#P3.43
Number of pages26
JournalElectronic Journal of Combinatorics
Volume22
Issue number3
Publication statusPublished - 4 Sep 2015

Keywords

  • Four-regular rigid vertex graphs
  • realization of genus ranges
  • unsigned Gauss codes

Fingerprint Dive into the research topics of 'Genus Ranges of 4-Regular Rigid Vertex Graphs'. Together they form a unique fingerprint.

Cite this