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

Duke, Richard A.

Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 817-822

Résumé

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.

Détail

DOI : 10.4153/CJM-1966-081-6

Bibliographie

[1] 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] 2. Edmonds, J. R., A combinatorial representation for polyhedral surfaces, Amer. Math. Soc. Not., 7 (1960), 646. Google Scholar

[3] 3. Youngs, J. W. T., Minimal imbeddings and the genus of a graph, J. Math. Mech., 12 (1963), 303–315. Google Scholar

[4] 4. Youngs, J. W. T., Irreducible graphs, Bull. Amer. Math. Soc., 70 (1964), 404–406. Google Scholar