A subgroup of the automorphism group of a graph Γ is said to be half-arc-transitive on Γ if its action on Γ is transitive on the vertex set of Γ and on the edge set of Γ but not on the arc set of Γ. ...Tetravalent graphs of girths 3 and 4 admitting a half-arc-transitive group of automorphisms have previously been characterized. In this paper we study the examples of girth 5. We show that, with two exceptions, all such graphs only have directed 5-cycles with respect to the corresponding induced orientation of the edges. Moreover, we analyze the examples with directed 5-cycles, study some of their graph theoretic properties and prove that the 5-cycles of such graphs are always consistent cycles for the given half-arc-transitive group. We also provide infinite families of examples, classify the tetravalent graphs of girth 5 admitting a half-arc-transitive group of automorphisms relative to which they are tightly-attached and classify the tetravalent half-arc-transitive weak metacirculants of girth 5.
On the Cayleyness of Praeger-Xu graphs Jajcay, R.; Potočnik, P.; Wilson, S.
Journal of combinatorial theory. Series B,
January 2022, 2022-01-00, Letnik:
152
Journal Article
Recenzirano
This paper discusses a family of graphs, called Praeger-Xu graphs and denoted PX(n,k) here, introduced by C.E. Praeger and M.-Y. Xu in 1989. These tetravalent graphs are distinguished by having large ...symmetry groups; their vertex-stabilizers can be arbitrarily larger than the number of vertices in the graph. This paper does the following: (1) exhibits a connection between vertex-transitive groups of symmetries in a Praeger-Xu graph and certain linear codes, (2) characterizes those linear codes, (3) characterizes Praeger-Xu graphs PX(n,k) which are Cayley, (4) shows that every PX(n,k) is quasi-Cayley, and (5) constructs an infinite family of Praeger-Xu graphs in which a smallest vertex-transitive group of symmetries has arbitrarily large vertex-stabiliser.
ON THE CAYLEYNESS OF PRAEGER–XU GRAPHS BARBIERI, MARCO; GRAZIAN, VALENTINA; SPIGA, PABLO
Bulletin of the Australian Mathematical Society,
12/2022, Letnik:
106, Številka:
3
Journal Article
Recenzirano
Odprti dostop
We give a sufficient and necessary condition for a Praeger–Xu graph to be a Cayley graph.
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.
We introduce the concept of
pseudocover
, which is a counterpart of
cover
, for symmetric graphs. The only known example of pseudocovers of symmetric graphs so far was given by Praeger, Zhou and the ...first-named author a decade ago, which seems technical and hard to extend to obtain more examples. In this paper, we present a criterion for a symmetric extender of a symmetric graph to be a pseudocover, and then apply it to produce various examples of pseudocovers, including (1) with a single exception, each Praeger–Xu’s graph is a pseudocover of a wreath graph; (2) each connected tetravalent symmetric graph with vertex stabilizer of size divisible by 32 has connected pseudocovers.
In order to complete (and generalize) results of Gardiner and Praeger on 4-valent symmetric graphs 3 we apply the method of lifting automorphisms in the context of elementary-abelian covering ...projections. In particular, the vertex- and edge-transitive graphs whose quotient by a normal p-elementary abelian group of automorphisms, for p an odd prime, is a cycle, are described in terms of cyclic and negacyclic codes. Specifically, the symmetry properties of such graphs are derived from certain properties of the generating polynomials of cyclic and negacyclic codes, that is, from divisors of xn±1∈Zpx. As an application, a short and unified description of resolved and unresolved cases of Gardiner and Praeger are given.
This is the first in the series of articles stemming from a systematical investigation of finite edge-transitive tetravalent graphs, undertaken recently by the authors. In this article, we study a ...special but important case in which the girth of such graphs is at most 4. In particular, we show that, except for a single arc-transitive graph on 14 vertices, every edge-transitive tetravalent graph of girth at most 4 is the skeleton of an arc-transitive map on the torus or has one of these two properties:
(1)
there exist two vertices sharing the same neighbourhood,
(2)
every edge belongs to exactly one girth cycle.
Graphs with property (1) or (2) are then studied further. It is shown that they all arise either as subdivided doubles of smaller arc-transitive tetravalent graphs, or as line graphs of triangle-free
(
G
,
1
)
-regular and
(
G
,
2
)
-arc-transitive cubic graphs, or as partial line graphs of certain cycle decompositions of smaller tetravalent graphs.
PDF