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
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
maximum genus
0 references
embedding
0 references
surface
0 references
Betti number
0 references