Maximum genus and connectivity Academic Article uri icon

abstract

  • It is shown that [(G)/3] is the tight lower bound on the maximum genus M(G) of 2-edge-connected simplicial graphs, where (G) is the cycle rank of the graph G. Also, a systematic method is developed to construct 3-vertex-connected simplicial graphs G satisfying the equality M(G) = [(G)/3]. These two results combine with previously known results to yield a complete picture of the tight lower bounds on the maximum genus of simplicial graphs.

published proceedings

  • Discrete Mathematics

author list (cited authors)

  • Chen, J., Archdeacon, D., & Gross, J. L.

citation count

  • 25

complete list of authors

  • Chen, Jianer||Archdeacon, Dan||Gross, Jonathan L

publication date

  • February 1996