We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Lower Bound of the Number of Maximum Genus Embeddings and Genus Embeddings of K.
- Authors
Han, Ren; Yanbo, Gao
- Abstract
In this paper, we study lower bound of the number of maximum orientable genus embeddings (or MGE in short) for a loopless graph. We show that a connected loopless graph of order n has at least $${\frac{1}{4^{\gamma_M(G)}}\prod_{v\in{V(G)}}{(d(v)-1)!}}$$ distinct MGE's, where γ( G) is the maximum orientable genus of G. Infinitely many examples show that this bound is sharp (i.e., best possible) for some types of graphs. Compared with a lower bound of Stahl (Eur J Combin 13:119-126, 1991) which concerns upper-embeddable graphs (i.e., embedded graphs with at most two facial walks), this result is more general and effective in the case of (sparse) graphs permitting relative small-degree vertices. We also obtain a similar formula for maximum nonorientable genus embeddings for general graphs. If we apply our orientable results to the current graph G of K, then G has at least 2 distinct MGE's.This implies that K has at least (22) nonisomorphic cyclic oriented triangular embeddings for sufficient large s.
- Subjects
EMBEDDINGS (Mathematics); GRAPH theory; GRAPHIC methods; VERTEX operator algebras; CYCLIC permutations; MATHEMATICAL diagrams; COMBINATORICS
- Publication
Graphs & Combinatorics, 2011, Vol 27, Issue 2, p187
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-010-0969-y