Abstract Suppose that $$\Delta $$ Δ is a thick, locally finite and locally s -arc transitive G -graph with $$s \ge 4$$ s ≥ 4 . For a vertex z in $$\Delta $$ Δ , let $$G_z$$ G z be the stabilizer of z ...and $$G_z^{1}$$ G z 1 the kernel of the action of $$G_z$$ G z on the neighbours of z . We say $$\Delta $$ Δ is of pushing up type provided there exist a prime p and a 1-arc ( x , y ) such that $$C_{G_z}(O_p(G_z^{1})) \le O_p(G_z^{1})$$ C G z ( O p ( G z 1 ) ) ≤ O p ( G z 1 ) for $$z \in \{x,y\}$$ z ∈ { x , y } and $$O_p(G_x^{1}) \le O_p(G_y^{1})$$ O p ( G x 1 ) ≤ O p ( G y 1 ) . We show that if $$\Delta $$ Δ is of pushing up type, then $$O_p(G_x^{1})$$ O p ( G x 1 ) is elementary abelian and $$G_x/G_x^{1}\cong X$$ G x / G x 1 ≅ X with $$ \textrm{PSL}_2(p^a)\le X \le \mathrm{P\Gamma L}_2(p^a)$$ PSL 2 ( p a ) ≤ X ≤ P Γ L 2 ( p a ) .
Let Γ be a graph with its automorphism group G and s(⩾0) an integer. We call a vertex sequence (v0,v1,…,vs) of length s+1 of Γ an s-arc if two consecutive vertices are adjacent and vi≠vi+2 for ...0⩽i⩽s−2. Γ is called s-arc-transitive if G acts on its s-arc set transitively. If Γ is s-arc-transitive, but not (s+1)-arc-transitive, we call it an s-transitive graph. Γ is a partial cube if Γ can be embedded into a hypercube isometrically. In this paper, we characterized non-trivial regular 2-arc-transitive partial cubes as three classes of graphs: hypercubes, doubled Odd graphs and even cycles. As a corollary, we prove that there exist no regular s-transitive partial cubes for s⩾4 and characterized regular s-transitive partial cubes for s=2 or 3.
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.
The k-dimensional Weisfeiler-Leman algorithm (k-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of k-WL to recognition of graph properties. Let G be ...an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of 2-WL on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then k-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless k=Ω(n). Similar results are obtained for recognition of arc-transitivity. Our lower bounds are based on an analysis of the Cai-Fürer-Immerman construction, which might be of independent interest. In particular, we provide sufficient conditions under which the Cai-Fürer-Immerman graphs can be made colorless.
•The Weisfeiler-Leman algorithm is used to recognize vertex-transitivity of graphs with a prime number of vertices•This is perhaps the first example of using it for recognition of a natural graph property rather than for isomorphism testing•This is no longer possible if the number of vertices is divisible by 16•The negative result is based on an analysis of the Cai-Fürer-Immerman construction•This analysis might be of independent interest as it provides a very straight way of making the CFI graphs colorless
A transitive permutation group is semiprimitive if each of its normal subgroups is transitive or semiregular. Interest in this class of groups is motivated by two sources: problems arising in ...universal algebra related to collapsing monoids and the graph-restrictive problem for permutation groups. Here we develop a theory of semiprimitive groups which encompasses their structure, their quotient actions and a method by which all finite semiprimitive groups are constructed. We also extend some results from the theory of primitive groups to semiprimitive groups, and conclude with open problems of a similar nature.
Let Δ be a connected graph, without loops or multiple edges, such that each vertex has valency at least 3. Let {x,y} be an edge. Let G⩽Aut(Δ) acting locally s-arc transitively on Δ with |Gz|<∞ for ...all z∈{x,y}. The amalgam (Gx,Gy;Gx,y) is determined in the case where s⩾4 and there doesn't exist a prime p for which Δ is of local characteristic p with respect to G.
We study s-arc-transitive graphs with s⩾2, and give a characterisation of the actions of vertex-transitive normal subgroups. An interesting consequence of this characterisation states that each ...non-bipartite 3-arc-transitive graph is a normal cover of a 2-arc-transitive graph admitting a simple group, or a locally primitive graph admitting a simple group with a soluble vertex stabiliser.
PDF
