A graph is symmetric if its automorphism group is transitive on the arc set of the graph. In this paper, we give a complete classification of connected pentavalent symmetric graphs of order 18
p
, ...for each prime
p
. It is shown that, such graphs there exist if and only if
p
= 2, 7 or 19, and up to isomorphism, there are only four such graphs.
A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let n be a product of three primes. The problem on the classification of the ...tetravalent half-arc-transitive graphs of order n has been considered by Xu (1992), Feng et al. (2007) and Wang and Feng (2010), and it was solved for the cases where n is a prime cube or twice a product of two primes. In this paper, we solve this problem for the remaining cases. In particular, there exist some families of these graphs which have a solvable automorphism group but are not metacirculants.
This paper determines all arc-transitive pentavalent graphs of order $4pq$, where $p,q\ge 5$ are distinct primes. The cases $q=1,2,3$ and $q=p$ is a prime have been treated previously by Hua et al. ...Pentavalent symmetric graphs of order $2pq$, Discrete Math. 311 (2011), 2259-2267, Hua and Feng Pentavalent symmetric graphs of order $8p$, J. Beijing Jiaotong University 35 (2011), 132-135, Guo et al. Pentavalent symmetric graphs of order $12p$, Electronic J. Combin. 18 (2011), #P233 and Huang et al. Pentavalent symmetric graphs of order four time a prime power, submitted for publication, respectively.
A graph
Γ is
symmetric if its automorphism group acts transitively on the arcs of
Γ, and
s-regular if its automorphism group acts regularly on the set of
s-arcs of
Γ. Tutte (1947, 1959) showed that ...every finite symmetric cubic graph is
s-regular for some
s
⩽
5
. Djoković and Miller (1980) proved that there are seven types of arc-transitive group action on finite cubic graphs, characterised by the stabilisers of a vertex and an edge. A given finite symmetric cubic graph, however, may admit more than one type of arc-transitive group action. In this paper we determine exactly which combinations of types are possible. Some combinations are easily eliminated by existing theory, and others can be eliminated by elementary extensions of that theory. The remaining combinations give 17 classes of finite symmetric cubic graph, and for each of these, we prove the class is infinite, and determine at least one representative. For at least 14 of these 17 classes the representative we give has the minimum possible number of vertices (and we show that in two of these 14 cases every graph in the class is a cover of the smallest representative), while for the other three classes, we give the smallest examples known to us. In an appendix, we give a table showing the class of every symmetric cubic graph on up to 768 vertices.
A Cayley graph
Γ
=
Cay
(
G
,
S
)
is said to be normal if
G
is normal in
Aut
Γ
. The concept of normal Cayley graphs was first proposed by Xu (Discrete Math 182:309–319,
1998
) and it plays an ...important role in determining the full automorphism groups of Cayley graphs. In this paper, we study the normality of connected arc-transitive pentavalent Cayley graphs
Γ
on finite nonabelian simple groups
G
, where the vertex stabilizer
A
v
is soluble for
A
=
Aut
Γ
and
v
∈
V
Γ
. We prove that
Γ
is either normal or
G
=
A
39
or
A
79
. Further, a connected pentavalent arc-transitive non-normal Cayley graph on
A
79
is constructed. To our knowledge, this is the first known example of pentavalent 3-arc-transitive Cayley graph on finite nonabelian simple group which is non-normal.
The subdivision graph S(Σ) of a graph Σ is obtained from Σ by ‘adding a vertex’ in the middle of every edge of Σ. Various symmetry properties of S(Σ) are studied. We prove that, for a connected graph ...Σ, S(Σ) is locally s-arc transitive if and only if Σ is ⌈s+12⌉-arc transitive. The diameter of S(Σ) is 2d+δ, where Σ has diameter d and 0⩽δ⩽2, and local s-distance transitivity of S(Σ) is defined for 1⩽s⩽2d+δ. In the general case where s⩽2d−1 we prove that S(Σ) is locally s-distance transitive if and only if Σ is ⌈s+12⌉-arc transitive. For the remaining values of s, namely 2d⩽s⩽2d+δ, we classify the graphs Σ for which S(Σ) is locally s-distance transitive in the cases, s⩽5 and s⩾15+δ. The cases max{2d,6}⩽s⩽min{2d+δ,14+δ} remain open.
A graph is
half-arc-transitive
if its automorphism group acts transitively on vertices and edges, but not on arcs. Let
p
be a prime. A graph is called a
p
-graph
if it is a Cayley graph of order a ...power of
p
. In this paper, a characterization is given of tetravalent edge-transitive
p
-graphs with
p
an odd prime. This is then applied to construct infinitely many connected tetravalent half-arc-transitive non-normal
p
-graphs with
p
an odd prime, and to initiate an investigation of tetravalent half-arc-transitive non-metacirculant
p
-graphs with
p
an odd prime. As by-products, two problems reported in the literature are answered.
In this paper, a complete classification is achieved of all the regular covers of the complete bipartite graphs
K
n
,
n
with cyclic covering transformation group, whose fibre-preserving automorphism ...group acts 2-arc-transitively. All these covers consist of one threefold covers of
K
6
,
6
, one twofold cover of
K
12
,
12
and one infinite family
X
(
r
,
p
) of
p
-fold covers of
K
p
r
,
p
r
with
p
a prime and
r
an integer such that
p
r
≥
3
. This infinite family
X
(
r
,
p
) can be derived by a very simple and nice voltage assignment
f
as follows:
X
(
r
,
p
)
=
K
p
r
,
p
r
×
f
Z
p
, where
K
p
r
,
p
r
is a complete bipartite graph with the bipartition
V
=
{
α
|
α
∈
V
(
r
,
p
)
}
∪
{
α
′
|
α
∈
V
(
r
,
p
)
}
for the
r
-dimensional vector space
V
(
r
,
p
) over the field of order
p
and
f
α
,
β
′
=
∑
i
=
1
r
a
i
b
i
,
for
all
α
=
(
a
i
)
r
,
β
=
(
b
i
)
r
∈
V
(
r
,
p
)
.
Hua et al. (Discrete Math 311, 2259–2267,
2011
) and Yang et al. (Discrete Math. 339, 522–532,
2016
) classify arc-transitive pentavalent graphs of order 2
pq
and of order 2
pqr
(with
p
,
q
,
r
...distinct odd primes), respectively. In this paper, we extend their results by giving a classification of arc-transitive pentavalent graphs of any square-free order.
PDF
