Genus Ranges of 4-Regular Rigid Vertex Graphs
Genus Ranges of 4-Regular Rigid Vertex Graphs
复制标题
DOI：
10.37236/3825
复制
发表时间：
2012-11
影响因子：
0.7
通讯作者：
D. Buck;Egor Dolzhenko;N. Jonoska;M. Saito;Karin Valencia
中科院分区：
文献类型：
--
作者：
D. Buck;Egor Dolzhenko;N. Jonoska;M. Saito;Karin Valencia
图的刚性顶点是指其关联边具有指定循环序的顶点。研究了4-正则刚性顶点图的可定向亏格范围。（可定向）亏格范围是一个图在所有可定向曲面上的亏格值的集合，刚性顶点图的嵌入要求在每个顶点上的关联边保持预定的循环序. 4-正则刚性顶点图的亏格范围是连续整数的集合，我们解决了两个问题：哪些整数区间作为这类图的亏格范围，以及什么类型的图实现给定的亏格范围.对于顶点数为2n（n > 1）的图，我们证明了所有的区间[a，B]（其中a < B ≤ n）和单点[h，h]（其中h ≤ n）都是亏格值域.对于顶点数为2n - 1（n ≥ 1）的图，我们证明了对于除[0，n]以外的所有a < B ≤ n，所有区间[a，B]和对于某些h ≤ n，所有区间[h，h]都是亏格值域.我们还提供了实现这些范围的图的构造。
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.