•The paper completely finish the classification of symmetric graphs of valency 4 having a quasi-semiregular automorphism, while its partial work for automorphism group being 2-arc-transitive or ...solvable was done in a former paper in Feng et al. (2019).•The method in this paper is completely different from the method in Feng et al. (2019). In fact, the former paper in 2019 mainly solved the case when a stabilizer has a bound, and this paper solve the case when a stabilizer has no bound.•The method in this paper combines group theory and graph theory, and in particular, group theory is widely used, including the well-known classification of non-abelian simple groups.•The research on the topic of this paper began in 2013, and this was proposed by Kutnar, Malnič, Martínez and Marušič as a kind of symmetry of graphs. After 2013, nearly no much work has been done except the above mentioned work in 2019.
Feng et al. (2019) characterized connected G-symmetric graphs of valency 4 having a quasi-semiregular automorphism, namely, a graph automorphism fixing a unique vertex in the vertex set of the graph and keeping the lengths of all other orbits equal, when G is soluble or the vertex stabilizer in G is not a 2-group. In this paper we prove that a connected symmetric graph with valency 4 having a quasi-semiregular automorphism is a Cayley graph on a group G with respect to S, where G is abelian of odd order and S is an orbit of a group of automorphisms of the group G.
An automorphism of a graph is called quasi-semiregular if it fixes a unique vertex of the graph and its remaining cycles have the same length. This kind of symmetry of graphs was first investigated ...by Kutnar, Malnič, Martínez and Marušič in 2013, as a generalization of the well-known problem regarding existence of semiregular automorphisms in vertex-transitive graphs. Symmetric graphs of valency three or four, admitting a quasi-semiregular automorphism, have been classified in recent two papers (Feng et al., 2019 11) and (Yin and Feng, 2021 42).
Let Γ be a connected symmetric graph of prime valency p≥5 admitting a quasi-semiregular automorphism. In this paper, it is proved that either Γ is a connected Cayley graph Cay(M,S) such that M is a 2-group admitting a fixed-point-free automorphism of order p with S as an orbit of involutions, or Γ is a normal N-cover of a T-arc-transitive graph of valency p admitting a quasi-semiregular automorphism, where T is a non-abelian simple group and N is a nilpotent group. Further, for p=5 a complete classification of graphs Γ such that either Aut(Γ) has a solvable arc-transitive subgroup or Γ is T-arc-transitive with T a non-abelian simple group is given. Finally, a construction of an infinite family of symmetric graphs admitting a quasi-semiregular automorphism and having nonsolvable automorphism group is given.
An automorphism ρ of a graph X is said to be semiregular provided all of its cycles in its cycle decomposition are of the same length, and is said to be simplicial if it is semiregular and the ...quotient multigraph Xρ of X with respect to ρ is a simple graph, and thus of the same valency as X. It is shown that, with the exception of the complete graph K4, the Petersen graph, the Coxeter graph and the so called H-graph (alternatively denoted as S(17), the smallest graph in the family of the so called Sextet graphs S(p), p≡±1(mod16)), every cubic arc-transitive graph with a primitive automorphism group admits a simplicial automorphism.
A non-trivial automorphism g of a graph Γ is called semiregular if the only power gi fixing a vertex is the identity mapping, and it is called quasi-semiregular if it fixes one vertex and the only ...power gi fixing another vertex is the identity mapping. In this paper, we prove that K4, the Petersen graph and the Coxeter graph are the only connected cubic arc-transitive graphs admitting a quasi-semiregular automorphism, and K5 is the only connected tetravalent 2-arc-transitive graph admitting a quasi-semiregular automorphism. It will also be shown that every connected tetravalent G-arc-transitive graph, where G is a solvable group containing a quasi-semiregular automorphism, is a normal Cayley graph of an abelian group of odd order.
It is shown that a vertex-transitive graph of valency
p
+
1
,
p a prime, admitting a transitive action of a
{
2
,
p
}
-group, has a non-identity semiregular automorphism. As a consequence, it is ...proved that a quartic vertex-transitive graph has a non-identity semiregular automorphism, thus giving a partial affirmative answer to the conjecture that all vertex-transitive graphs have such an automorphism and, more generally, that all 2-closed transitive permutation groups contain such an element (see D. Marušič, On vertex symmetric digraphs, Discrete Math. 36 (1981) 69–81; P.J. Cameron (Ed.), Problems from the Fifteenth British Combinatorial Conference, Discrete Math. 167/168 (1997) 605–615).
The polycirculant conjecture asserts that every vertex-transitive digraph has a semiregular automorphism: a non-trivial automorphism whose cycles all have the same length. In this paper, we ...investigate the existence of semiregular automorphisms of edge-transitive graphs. In particular, we show that any regular edge-transitive graph of valency three or four has a semiregular automorphism.
PDF
