Geodesic
Genus ranges of 4-regular rigid vertex graphs
Dorothy Buck1 ; Egor Dolzhenko2 ; Natasa Jonoska3 ; Masahico Saito3 ; Karin Valencia4
1Imperial College London
2University of Southern California
3University of South Florida
4European Molecular Biology Laboratory
The electronic journal of combinatorics, Tome 22 (2015) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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, 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 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.
DOI : 10.37236/3825
Classification : 05C10, 57M15
Mots-clés : four-regular rigid vertex graphs, realization of genus ranges, unsigned Gauss codes

Dorothy Buck  1   ; Egor Dolzhenko  2   ; Natasa Jonoska  3   ; Masahico Saito  3   ; Karin Valencia  4

1 Imperial College London
2 University of Southern California
3 University of South Florida
4 European Molecular Biology Laboratory 
@article{10_37236_3825,
     author = {Dorothy Buck and Egor Dolzhenko and Natasa Jonoska and Masahico Saito and Karin Valencia},
     title = {Genus ranges of 4-regular rigid vertex graphs},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {3},
     doi = {10.37236/3825},
     zbl = {1323.05037},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3825/}
}
TY  - JOUR
AU  - Dorothy Buck
AU  - Egor Dolzhenko
AU  - Natasa Jonoska
AU  - Masahico Saito
AU  - Karin Valencia
TI  - Genus ranges of 4-regular rigid vertex graphs
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3825/
DO  - 10.37236/3825
ID  - 10_37236_3825
ER  - 
%0 Journal Article
%A Dorothy Buck
%A Egor Dolzhenko
%A Natasa Jonoska
%A Masahico Saito
%A Karin Valencia
%T Genus ranges of 4-regular rigid vertex graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3825/
%R 10.37236/3825
%F 10_37236_3825
Dorothy Buck; Egor Dolzhenko; Natasa Jonoska; Masahico Saito; Karin Valencia. Genus ranges of 4-regular rigid vertex graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 3. doi: 10.37236/3825

Cité par Sources :