Upper embeddability of graphs (Q1128130)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Upper embeddability of graphs
scientific article

    Statements

    Upper embeddability of graphs (English)
    0 references
    0 references
    0 references
    2 August 2000
    0 references
    The maximum genus of a graph \(G\) is the largest integer \(k\) such that \(G\) has a cellular embedding in the orientable surface of genus \(k\). Denote the maximum genus by \(\gamma_M(G)\). If \(\beta(G)\) is the Betti number of \(G\), then \(\chi_M(G)\leq \left[{\beta(G)\over 2}\right]\), the largest integer in \(\beta(G)/2\). A graph is upper embeddable if \(\gamma_M(G)= \left[{\beta(G)\over 2}\right]\); or equivalently, the graph has an embedding with one face if \(\beta(G)\) is even or two faces if \(\beta(G)\) is odd. The main result of the paper is the following theorem: Suppose \(G\) is a graph without loops. If \(G\) can be embedded on a surface (orientable or not) such that the size of each face is no more than 5, then \(G\) is upper embeddable.
    0 references
    0 references
    maximum genus
    0 references
    embedding
    0 references
    surface
    0 references
    Betti number
    0 references

    Identifiers