Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-20T16:31:34.403Z Has data issue: false hasContentIssue false
  • English
  • Français

The Genus, Regional Number, and Betti Number of a Graph

Published online by Cambridge University Press:  20 November 2018

Richard A. Duke
Richard A. Duke*
Affiliation:
University of Washington, Seattle, Wash.
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let the genus of an orientable 2-manifold M be denoted by γ(M). The genus, γ(G), of a graph G is then the smallest of the numbers γ(N) for orientable 2-manifolds N in which G can be embedded. An embedding of G in M is called minimal if γ(G) = γ(M). When each component of the complement of G in M is an open 2-cell, the embedding of G in M is called a 2-cell embedding. In (3), J. W. T. Youngs has shown that each minimal embedding is a 2-cell embedding. It follows from the results of (3) that for each graph G, there is a number d(G), called the regional number, such that for any 2-cell embedding of G in an orientable 2-manifold, the number of (2-cell) complementary domains of G is ⩽d(G), with equality holding if and only if the embedding is minimal.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 18 , 1966 , pp. 817 - 822
Copyright
Copyright © Canadian Mathematical Society 1966

References

1. Brown, T. A. and Duke, R. A., An irreducible graph consisting of a single block, J. Math. Mech., 15 (1966), 129–135.Google Scholar
2. Edmonds, J. R., A combinatorial representation for polyhedral surfaces, Amer. Math. Soc. Not., 7 (1960), 646.Google Scholar
3. Youngs, J. W. T., Minimal imbeddings and the genus of a graph, J. Math. Mech., 12 (1963), 303–315.Google Scholar
4. Youngs, J. W. T., Irreducible graphs, Bull. Amer. Math. Soc., 70 (1964), 404–406.Google Scholar