In the late 1990s, Graver and Watkins initiated the study of all edge‐transitive maps. Recently, Gareth Jones revisited the study of such maps and suggested classifying the maps in terms of either ...their automorphism groups or their underlying graphs. A natural step towards classifying edge‐transitive maps is to study the arc‐transitive ones. In this paper, we investigate the connection of a class of arc‐transitive maps to consistent cycles of the underlying graph, with special emphasis on maps of smallest possible valence, namely 4. We give a complete classification of arc‐transitive maps whose underlying graphs are arc‐transitive Rose Window graphs.
A well-known theorem of Sabidussi shows that a simple G-arc-transitive graph can be represented as a coset graph for the group G. This pivotal result is the standard way to turn problems about simple ...arc-transitive graphs into questions about groups. In this paper, the Sabidussi representation is extended to arc-transitive, not necessarily simple graphs which satisfy a local-finiteness condition: namely graphs with finite valency and finite edge-multiplicity. The construction yields a G-arc-transitive coset graph Cos(G,H,J), where H,J are stabilisers in G of a vertex and incident edge, respectively. A first major application is presented concerning arc-transitive maps on surfaces: given a group G=〈a,z〉 with |z|=2 and |a| finite, the coset graph Cos(G,〈a〉,〈z〉) is shown, under suitable finiteness assumptions, to have exactly two different arc-transitive embeddings as a G-arc-transitive map (V,E,F) (with V,E,F the sets of vertices, edges and faces, respectively), namely, a G-rotary map if |az| is finite, and a G-bi-rotary map if |zza| is finite. The G-rotary map can be represented as a coset geometry for G, extending the notion of a coset graph. However the G-bi-rotary map does not have such a representation, and the face boundary cycles must be specified in addition to incidences between faces and edges. In addition a coset geometry construction is given of a flag-regular map (V,E,F) for non necessarily simple graphs. For all of these constructions it is proved that the face boundary cycles are simple cycles precisely when the given group acts faithfully on V∪F. Illustrative examples are given for graphs related to the n-dimensional hypercubes and the Petersen graph.
•Classifying all regular maps of a given graphs is a core problem in topological graph theory. A 2-cell embedding of a connected graph into a connected closed surface is called a topological map.•The ...main results of the paper is important and interesting. Orientably regular embeddings of graphs of orders p, pq (where p and q are primes) have already been classified. A natural problem is to determine the orientably regular embeddings of graphs of order p3, where p is a prime. The problem of classifying such embedding should be more complicated than the previously settled cases.
Let G be the automorphism group of an orientably regular embedding of a connected simple graph of order p3, where p is a prime. It was shown in 19 that except for the case when p=2 and G=S4, G contains a normal Sylow p-subgroup P of order pk where k∈{3,4,5}, while such embeddings with k=5 were determined. In this paper, a further classification is achieved for all such embeddings with k=3.
A graph Γ is symmetric or arc-transitive if its automorphism group Aut(Γ) is transitive on the arc set of the graph. Let p be an odd prime. Pentavalent symmetric graphs of order 2pn with n ≥ 2 have ...been considered by Pan et al. in Algebra Colloq. 22 (2015) 383-394 and by Feng et al. in Discrete Math. 339 (2016) 2640-2651. This paper gives a depiction of pentavalent symmetric graphs of order 2mpn for any integers m ≥ 2 and n ≥ 1. As an application, connected pentavalent symmetric graphs of order 16p, 8p2 and 8p3 are classified.
A subgroup of the automorphism group of a graph acts half-arc-transitively on the graph if it acts transitively on the vertex-set and on the edge-set of the graph but not on the arc-set of the graph. ...If the full automorphism group of the graph acts half-arc-transitively, the graph is said to be half-arc-transitive.
In 1994 Gardiner and Praeger introduced two families of tetravalent arc-transitive graphs, called the C±1 and the C±ε graphs, that play a prominent role in the characterization of the tetravalent graphs admitting an arc-transitive group of automorphisms with a normal elementary abelian subgroup such that the corresponding quotient graph is a cycle. All of the Gardiner–Praeger graphs are arc-transitive but admit a half-arc-transitive group of automorphisms. Quite recently, Potočnik and Wilson introduced the family of CPM graphs, which are generalizations of the Gardiner–Praeger graphs. Most of these graphs are arc-transitive, but some of them are half-arc-transitive. In fact, at least up to order 1000, each tetravalent half-arc-transitive loosely-attached graph of odd radius having vertex-stabilizers of order greater than 2 is isomorphic to a CPM graph.
In this paper we determine the automorphism group of the CPM graphs and investigate isomorphisms between them. Moreover, we determine which of these graphs are 2-arc-transitive, which are arc-transitive but not 2-arc-transitive, and which are half-arc-transitive.
In this paper, a characterization of vertex primitive 2-arc-transitive Cayley graphs is given; in particular, all connected non-normal vertex primitive s-transitive Cayley graphs (up to isomorphism) ...are determined for s⩾2. Problem 1.1 raised by Li (2005) is solved partly.
A graph is half-arc-transitive if its full automorphism group acts transitively on vertices and edges, but not on arcs. Let p be a prime. It is known that there exists no tetravalent ...half-arc-transitive graph of order p or p2. All the tetravalent half-arc-transitive graphs of order p3 or p4 have been classified in two previous papers 9,23. As a continuation, in this paper, a classification is given of all tetravalent half-arc-transitive graphs of order p5.
Edge-transitive bi-Cayley graphs Conder, Marston; Zhou, Jin-Xin; Feng, Yan-Quan ...
Journal of combinatorial theory. Series B,
November 2020, 2020-11-00, Volume:
145
Journal Article
Peer reviewed
Open access
A graph Γ admitting a group H of automorphisms acting semi-regularly on the vertices with exactly two orbits is called a bi-Cayley graph over H. This generalisation of a Cayley graph gives a class of ...graphs that includes many important examples such as the Petersen graph, the Gray graph and the Hoffman-Singleton graph. A bi-Cayley graph Γ over a group H is called normal if H is normal in the full automorphism group of Γ, and almost-normal edge-transitive if the normaliser of H in the full automorphism group of Γ is transitive on the edges of Γ. In this paper, we give a characterisation of almost-normal edge-transitive bi-Cayley graphs, and in particular, we give a detailed description of 2-arc-transitive normal bi-Cayley graphs. Using this, we investigate three classes of bi-Cayley graphs, namely those over abelian groups, dihedral groups and metacyclic p-groups. We find that under certain conditions, ‘almost-normal edge-transitive’ is the same as ‘normal’ for graphs in these three classes. As a by-product, we obtain a complete classification of all connected trivalent edge-transitive graphs of girth at most 6. Also we answer some open questions from the literature about these and related classes of graphs, posed by Li (in Proc. Amer. Math. Soc. 133 (2005)), Marušič and Potočnik (in Eur. J. Comb. 22 (2001)) and Marušič and Šparl (in J. Algebr. Comb. 28 (2008)), and we correct a major error in a recent paper by Li, Song and Wang (in J. Comb. Theory Ser. A 120 (2013)).
A graph is called half-arc-transitive if its full automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, we classify hexavalent half-arc-transitive graphs of ...order 9p for each prime p. As a result, there are four infinite families of such graphs: three defined on Zp⋊Z27 with 27|(p−1); one defined on Z3p⋊Z9 with 9|(p−1).
It is known that there are precisely three transitive permutation groups of degree 6 that admit an invariant partition with three parts of size 2 such that the kernel of the action on the parts has ...order 4; these groups are called
A
4
(
6
),
S
4
(
6
d
) and
S
4
(
6
c
). For each
L
∈
{
A
4
(
6
)
,
S
4
(
6
d
)
,
S
4
(
6
c
)
}, we construct an infinite family of finite connected 6‐valent graphs
{
Γ
n
}
n
∈
N and arc‐transitive groups
G
n
≤
Aut
(
Γ
n
) such that the permutation group induced by the action of the vertex‐stabiliser
(
G
n
)
v on the neighbourhood of a vertex
v is permutation isomorphic to
L, and such that
∣
(
G
n
)
v
∣ is exponential in
∣
V
(
Γ
n
)
∣. These three groups were the only transitive permutation groups of degree at most 7 for which the existence of such a family was undecided. In the process, we construct an infinite family of cubic 2‐arc‐transitive graphs such that the dimension of the 1‐eigenspace over the field of order 2 of the adjacency matrix of the graph grows linearly with the order of the graph.
PDF
