Back to Search
Start Over
Minimum genus embeddings of the complete graph
- Source :
- Acta Mathematica Sinica, English Series. 32:1246-1254
- Publication Year :
- 2016
- Publisher :
- Springer Science and Business Media LLC, 2016.
-
Abstract
- In this paper, the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding (or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K 12s+8 in orientable surfaces, which show that there are at least $$\frac{10}{3} \times (\frac{200}{9})^s$$ distinct minimum genus embeddings for K 12s+8 in orientable surfaces. We have also proved that K 12s+8 has at least $$\frac{10}{3} \times (\frac{200}{9})^s$$ distinct minimum genus embeddings in non-orientable surfaces.
- Subjects :
- Discrete mathematics
Book embedding
Graph embedding
Applied Mathematics
General Mathematics
010102 general mathematics
0102 computer and information sciences
01 natural sciences
Combinatorics
010201 computation theory & mathematics
Genus (mathematics)
Petersen graph
Clique-width
Graph minor
Topological graph theory
0101 mathematics
Toroidal graph
Mathematics
Subjects
Details
- ISSN :
- 14397617 and 14398516
- Volume :
- 32
- Database :
- OpenAIRE
- Journal :
- Acta Mathematica Sinica, English Series
- Accession number :
- edsair.doi...........954c2c346c73e63ae4ca2c2f05df2b1f