A tight lower bound on the maximum genus of a simplicial graph Academic Article

abstract

• It is proved that every connected simplicial graph with minimum valence at least three has maximum genus at least one-quarter of its cycle rank. This follows from the technical result that every 3-regular simplicial graph except K4 has a Xuong co-tree whose odd components have only one edge each. It is proved, furthermore, that this lower bound is tight. However, examples are used to illustrate that it does not apply to non-simplicial graphs. This result on maximum genus leads to several immediate consequences for average genus.

authors

• Chen, Jianer

published proceedings

• DISCRETE MATHEMATICS

author list (cited authors)

• Chen, J., Kanchi, S. P., & Gross, J. L.

citation count

• 16

complete list of authors

• Chen, J||Kanchi, SP||Gross, JL

publication date

• September 1996

publisher

• Elsevier  Publisher

published in

• Discrete Mathematics  Journal

keywords

• 49 Mathematical Sciences
• 4901 Applied Mathematics
• 4904 Pure Mathematics

Digital Object Identifier (DOI)

• 10.1016/0012-365X(95)00070-D

start page

• 83

end page

• 102

volume

• 156

issue

• 1-3

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2F0012-365x%2895%2900070-d