Published in

Elsevier, European Journal of Combinatorics, 7(31), p. 1725-1734, 2010

DOI: 10.1016/j.ejc.2010.03.006

Links

Tools

Export citation

Search in Google Scholar

An infinite family of half-arc-transitive graphs with universal reachability relation

Journal article published in 2010 by Klavdija Kutnar, Dragan Marušič, Primož Šparl
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

The action of a subgroup G of automorphisms of a graph X is said to be half-arc-transitive if it is vertex-transitive and edge-transitive but not arc-transitive. In this case the graph X is said to be G-half-arc-transitive. In particular, when the graph X is said to be half-arc-transitive. Two oppositely oriented digraphs may be associated with any such graph in a natural way. The reachability relation of a graph admitting a half-arc-transitive group action is an equivalence relation defined on either of these two digraphs as follows. An arc e is reachable from an arc e′ if there exists an alternating path starting with e and ending with e′. The reachability relation is clearly universal for all vertex-primitive half-arc-transitive graphs. The smallest known vertex-primitive half-arc-transitive graphs have valency 14 and no such graphs of valency smaller than 10 exist. The natural framework for the question of the existence of half-arc-transitive graphs with universal reachability relation is therefore the family of vertex-imprimitive half-arc-transitive graphs, and in particular those of valency less than 14. It is known that no such graph of valency 4 exists (see D. Marušič, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B 73 (1998) 41–76). In this paper an infinite family of vertex-imprimitive half-arc-transitive graphs of valency 12 with universal reachability relation is constructed. These graphs have a solvable automorphism group but are not metacirculants.