| Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration |
| |
| 作者姓名： | LinFanMAO YanPeiLIU FengTIAN |
| |
| 作者单位： | [1]AcademyofMathematicsandSystemsScience,ChineseAcademyofSciences,Beijing100080,P.R.China [2]InstituteofAppliedMathematics,BeijingJiaotongUniversity,Beijing100044,P.R.China [3]AcademyofMathematicsandSystemsScience,ChineseAcademyofScience,Beijing100080,P.R.China |
| |
| 摘 要： | A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.
|
| 关 键 词： | 嵌入映射 卡利图 循环图 自同构群 |
| 收稿时间： | 21 September 2001 |
Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration |
| |
| LinFanMAO YanPeiLIU FengTIAN.Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration[J].Acta Mathematica Sinica,2005,21(2):225-236. |
| |
| Authors: | Lin Fan Mao Yan Pei Liu Feng Tian |
| |
| Institution: | (1) Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, P. R. China;(2) Institute of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, P. R. China;(3) Academy of Mathematics and Systems Science, Chinese Academy of Science, Beijing 100080, P. R. China |
| |
| Abstract: | A graph is called a semi–regular graph if its automorphism group action on its ordered pair of
adjacent vertices is semi–regular. In this paper, a necessary and sufficient condition for an automorphism
of the graph Γ to be an automorphism of a map with the underlying graph Γ is obtained. Using this
result, all orientation–preserving automorphisms of maps on surfaces (orientable and non–orientable) or
just orientable surfaces with a given underlying semi–regular graph Γ are determined. Formulas for the
numbers of non–equivalent embeddings of this kind of graphs on surfaces (orientable, non–orientable
or both) are established, and especially, the non–equivalent embeddings of circulant graphs of a prime
order on orientable, non–orientable and general surfaces are enumerated.
The first and the second authors are partially supported by NNSFC under Grant No. 60373030
The third author is partially supported by NNSFC under Grant No. 10431020 |
| |
| Keywords: | Embedding Map Cayley graph Circulant graph Symmetric graph Automorphism group Burnside Lemma |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
|
