The graphs with a symmetrical Euler cycle

Chen，Jiyong1; Li，Cai Heng2; Praeger，Cheryl E.3; Song，Shu Jiao4

2022

10.26493/2590-9770.1464.7cd

Art of Discrete and Applied Mathematics   Impact Factor & Quartile

2590-9770

The graphs in this paper are finite, undirected, and without loops, but may have more than one edge between a pair of vertices. If such a graph has ℓ edges, then an Euler cycle is a sequence (e, e,..., e) of these ℓ edges, each occurring exactly once, such that e, e are incident with a common vertex for each i (reading subscripts modulo ℓ). An Euler cycle is symmetrical if there exists an automorphism of the graph such that e → e for each i. The cyclic group generated by this automorphism has one orbit on edges if ℓ is odd, or two orbits of length ℓ/2 if ℓ is even: that is to say, the group is regular or bi-regular on edges, respectively. Symmetrical Euler cycles arise naturally from arc-transitive embeddings of graphs in surfaces since, for each face of the embedded graph, the sequence of edges on the boundary of the face forms a symmetrical Euler cycle for the induced subgraph on this edge-set. We first classify all finite connected graphs which admit a cyclic subgroup of automorphisms that is regular or bi-regular on edges, and identify more than a dozen infinite families of examples. We then prove that exactly six of these families consist of graphs with symmetrical Euler cycles. These are the (only) candidates for the induced subgraphs of the boundary cycles of the faces of arc-transitive maps.

arc-transitive maps edge-transitive graphs graph embeddings graphs with multiple edges

English

Others

National Natural Science Foundation of China[11771200];National Natural Science Foundation of China[11931005];National Natural Science Foundation of China[12101518];National Natural Science Foundation of China[61771019];Australian Research Council[DP160102323];Society for French Studies[ZR2020MA044];

2-s2.0-85134495499

Scopus

1.School of Mathematical Sciences,Xiamen University,Xiamen,China
2.Department of Mathematics,SUSTech International Center for Mathematics,Southern University of Science and Technology,Shenzhen,China
3.Department of Mathematics and Statistics,The University of Western Australia,Crawley,6009,Australia
4.School of Mathematics and Information Science,Yantai University,Yantai,China

Chen，Jiyong,Li，Cai Heng,Praeger，Cheryl E.,et al. The graphs with a symmetrical Euler cycle[J]. Art of Discrete and Applied Mathematics,2022,5(3).

Chen，Jiyong,Li，Cai Heng,Praeger，Cheryl E.,&Song，Shu Jiao.(2022).The graphs with a symmetrical Euler cycle.Art of Discrete and Applied Mathematics,5(3).

Chen，Jiyong,et al."The graphs with a symmetrical Euler cycle".Art of Discrete and Applied Mathematics 5.3(2022).