The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration |
| |
Authors: | Linfan Mao Yanpei Liu Erling Wei |
| |
Institution: | (1) Academy of Mathematics and Systems, Chinese Academy of Sciences, Beijing, 100080, People's Republic of China;(2) Institute of Applied Mathematics, Northern Jiaotong University, Beijing, 100044, People's Republic of China;(3) Information School, Renmin University of China, Beijing, 100872, People's Republic of China |
| |
Abstract: | A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted
maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing
the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc
automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings
on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable
surface with underlying graph a bouquet of cycles Bn, a closed-end ladder Ln or a Ringel ladder Rn. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is
established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable
surfaces with an underlying bouquet Bn in this paper. |
| |
Keywords: | Embedding Map Semi-arc Automorphism group Burnside lemma |
本文献已被 SpringerLink 等数据库收录! |
|