×

Square-free non-Cayley numbers. On vertex-transitive non-Cayley graphs of square-free order. (English) Zbl 1075.20002

A (finite) graph \(\Gamma\) is vertex-transitive if its automorphism group \(\operatorname{Aut}(\Gamma)\) acts transitively on the vertex set \(V(\Gamma)\); it is a Cayley graph if \(\operatorname{Aut}(\Gamma)\) contains a regular subgroup. The smallest vertex-transitive graph which is not a Cayley graph is the Petersen graph with \(10\) vertices. An integer \(n\) is called a non-Cayley number if there is a vertex-transitive graph which is not Cayley (written \(n\in\mathcal{NC}\)).
This class of integers was first studied by D. Marušič [Ars Comb. 16-B, 297-302 (1983; Zbl 0535.05034)] and since then a considerable amount has been learned of these numbers. For example, each integer in \(\mathcal{NC}\) is either square-free, equal to \(12\), or has the form \(p^2\) or \(p^3\) (\(p\) prime) [see B. McKay and C. E. Praeger, J. Graph Theory 22, No. 4, 321-334 (1996; Zbl 0864.05041)]. A series of authors have determined the integers in \(\mathcal{NC}\) which are a product of at most three distinct primes [see Á. Seress, Discrete Math. 182, No. 1-3, 279-292 (1998; Zbl 0908.05050)].
In the present paper the authors determine the square-free integers \(n\in\mathcal{NC}\) for which there is a graph \(\Gamma\) with \(n\) vertices such that \(\operatorname{Aut}(\Gamma)\) is ‘primitive’ on \(V(\Gamma)\) but \(\Gamma\) is not Cayley. These integers fall into seven (presumably) infinite classes and 16 exceptional degrees. The proof is based on the authors’ earlier classification of primitive permutation groups of square-free degree [C. H. Li and Á. Seress, Bull. Lond. Math. Soc. 35, No. 5, 635-644 (2003; Zbl 1043.20001)] together with a description (in the present paper) of the primitive permutation groups of square-free degree which contain a regular subgroup.
The main theorems imply the following corollaries: (1) all vertex-primitive Cayley graphs of square-free order are known; and (2) a group \(R\) of composite square-free order is not a \(B\)-group (Burnside group) if and only if \(R\cong\mathbb{Z}_{29}.\mathbb{Z}_7\), \(\mathbb{Z}_{31}.\mathbb{Z}_5\) or \(\mathbb{Z}_p.\mathbb{Z}_{(p-1)/2}\) for some prime \(p\equiv 3\bmod 4\).

MSC:

20B15 Primitive groups
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

Software:

GAP
PDFBibTeX XMLCite
Full Text: DOI

References:

[8] The GAP Group, GAP ? Groups, Algorithms, and Programming, Version 4.3; 2002, (http://www.gap-system.org).
[15] H. L. Li, J. Wang, L. Y. Wang and M. Y. Xu, Vertex primitive graphs of order containing a large prime factor, Comm. Algebra, Vol. 22, No. 9 (1994) pp. 3449-3477. · Zbl 0802.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.