On the number of genus one labeled circle trees
The electronic journal of combinatorics, Tome 14 (2007)
A genus one labeled circle tree is a tree with its vertices on a circle, such that together they can be embedded in a surface of genus one, but not of genus zero. We define an e-reduction process whereby a special type of subtree, called an e-graph, is collapsed to an edge. We show that genus is invariant under e-reduction. Our main result is a classification of genus one labeled circle trees through e-reduction. Using this we prove a modified version of a conjecture of David Hough, namely, that the number of genus one labeled circle trees on $n$ vertices is divisible by $n$ or $n/2$. Moreover, we explicitly characterize when each of these possibilities occur.
DOI :
10.37236/986
Classification :
05C30, 05C10, 05C05, 05C75, 05A99
Mots-clés : number of genus one labeled circle tree, e-reduction, e-graph
Mots-clés : number of genus one labeled circle tree, e-reduction, e-graph
@article{10_37236_986,
author = {Karola M\'esz\'aros},
title = {On the number of genus one labeled circle trees},
journal = {The electronic journal of combinatorics},
year = {2007},
volume = {14},
doi = {10.37236/986},
zbl = {1159.05028},
url = {http://geodesic.mathdoc.fr/articles/10.37236/986/}
}
Karola Mészáros. On the number of genus one labeled circle trees. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/986
Cité par Sources :