Semisymmetry of generalized Folkman graphs (Q5937426)

A graph \( \Gamma \) is said to be semisymmetric if it is regular and edge- but not vertex-transitive. The study of semisymmetric graphs was initiated by Folkman, who also introduced several families of such graphs. The authors generalize the original Folkman construction of semisymmetric graphs from abelian groups, and introduce a construction starting from a transitive permutation group and one of its orbitals. All graphs obtained in this manner are regular, bipartite, and edge-transitive, with at most two vertex orbits. A simple sufficient condition on the neighborhoods of vertices of the obtained graphs allows them to construct infinite families of semisymmetric graphs of orders a multiple of 4; some of them based on the ``usual'' action of the alternating group \( {\mathcal A}_n \). Using the action of the cyclic group \( {\mathcal Z}_n \), they obtain a family of tetracirculant graphs, i.e., graphs admitting an automorphism with exactly four vertex orbits of the same size. A further detailed investigation of semisymmetric tetracirculants leads to a classification of all semisymmetric graphs of order \( 4p \), where \( p \) is a prime. It is shown that for a given prime \( p \geq 7 \) and a positive integer \( d \), there exists a (unique) semisymmetric graph of order \( 4p \) and degree \( d \) if and only if \( d \) is an even number dividing \( p-1 \). Each of these graphs is a tetracirculant and a generalized Folkman graph.