A graph is called a semi-regular graph if its automorphism group action onits ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficientcondition for an automorphism of the graph Γ t...A graph is called a semi-regular graph if its automorphism group action onits ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficientcondition for an automorphism of the graph Γ to be an automorphism of a map with the underlyinggraph Γ is obtained. Using this result, all orientation-preserving automorphisms of maps onsurfaces (orientable and non-orientable) or just orientable surfaces with a given underlyingsemi-regular graph Γ are determined. Formulas for the numbers of non-equivalent embeddings of thiskind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, thenon-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable andgeneral surfaces are enumerated.展开更多
基金The first and the second authors are partially supported by NNSFC under Grant No.60373030The third author is partially supported by NNSFC under Grant No.10431020
文摘A graph is called a semi-regular graph if its automorphism group action onits ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficientcondition for an automorphism of the graph Γ to be an automorphism of a map with the underlyinggraph Γ is obtained. Using this result, all orientation-preserving automorphisms of maps onsurfaces (orientable and non-orientable) or just orientable surfaces with a given underlyingsemi-regular graph Γ are determined. Formulas for the numbers of non-equivalent embeddings of thiskind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, thenon-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable andgeneral surfaces are enumerated.
