Genus Ranges of 4-Regular Rigid Vertex Graphs

Abstract

We introduce a notion of genus range as a set of values of genera over all surfaces into which a graph is embedded cellularly, and we study the genus ranges of a special family of four-regular graphs with rigid vertices that has been used in modeling homologous DNA recombination. We show that the genus ranges are sets of consecutive integers. For any positive integer $n$, there are graphs with $2n$ vertices that have genus range $m,m+1,...,m^{\prime }$ for all $0\le m<m^{\prime }\le n$, and there are graphs with $2n-1$ vertices with genus range $m,m+1,...,m^{\prime }$ for all $0\le m<m^{\prime }<n$ or $0<m<m^{\prime }\le n$. Further, we show that for every $n$ there is $k<n$ such that $h$ is a genus range for graphs with $2n-1$ and $2n$ vertices for all $h\le k$. It is also shown that for every $n$, there is a graph with $2n$ vertices with genus range $0,1,...,n$, but there is no such a graph with $2n-1$ vertices.