A family of edge-transitive Cayley graphs
- PDF / 513,068 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 207 Views
A family of edge-transitive Cayley graphs Jiangmin Pan1 · Zhaofei Peng1
Received: 6 April 2017 / Accepted: 15 March 2018 char 169 Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract Edge-transitive graphs of order a prime or a product of two distinct primes with any positive integer valency, and of square-free order with valency at most 7 have been classified by a series of papers. In this paper, a complete classification is given of edge-transitive Cayley graphs of square-free order with valency less than the smallest prime divisor of the order. This leads to new constructions of infinite families of both arc-regular Cayley graphs and edge-regular Cayley graphs (so half-transitive). Also, as by-products, it is proved that, for any given positive integers k, s ≥ 1 and m, n ≥ 2, there are infinitely many arc-regular normal circulants of valency 2k and order a product of s primes, and there are infinitely many edge-regular normal metacirculants of valency 2m and order a product of n primes; such arc-regular and edge-regular examples are also specifically constructed. Keywords Edge-transitive graph · Half-transitive graph · Arc-regular graph · Edge-regular graph · Normal Cayley graph Mathematics Subject Classification 20B15 · 20B30 · 05C25
This work was partially supported by National Natural Science Foundation of China (11461007, 11231008).
B 1
Jiangmin Pan [email protected] School of Statistics and Mathematics, Yunnan University of Finance and Economics, Kunming, People’s Republic of China
123
J Algebr Comb
1 Introduction For a graph Γ , if its full automorphism group AutΓ is transitive on its vertex set, edge set or arc set, then Γ is called vertex-transitive, edge-transitive or arc-transitive, respectively. An arc-transitive graph is edge-transitive. In particular, if AutΓ is regular on the arc set or the edge set of Γ , then Γ is called arc-regular or edge-regular, respectively; if AutΓ is transitive on both vertex set and edge set of Γ , but intransitive on the arc set of Γ , then Γ is called half-transitive. Edge-transitive graphs of square-free order (namely, not divisible by any prime square) provide a rich source of many interesting families of graphs, and have a rich research history. In 1971, Chao [6] classified arc-transitive graphs of prime order p, then Cheng and Oxley [7] classified edge-transitive graphs of order 2 p, and Wang and Xu [29] classified arc-transitive graphs of order 3 p. These results were generalized to the case of order a product of two distinct primes by Praeger et al. [26,27]. Moreover, edge-transitive graphs of square-free order and valency at most 7 have been classified by [9,17,19,20]. Quite recently, Li et al. [18] characterized the ‘basic’ edge-transitive graphs (namely, each nontrivial normal subgroup of the edge-transitive automorphism group has at most two orbits on the vertex set) of square-free order, with certain cases needing further research. It seems difficult to approach a general classification of edgetransitive graphs of square-free or
Data Loading...
