5339152
C O ] 7 F eb 2 00 7 ON QUARTIC HALF-ARC-TRANSITIVE METACIRCULANTS
Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)semiregular for some integers m ≥ 1, n ≥ 2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ has at least one fixed vertex. A half-arc-transitive graph is a vertexand edgebut not arc-transitive graph. In this article quartic half-arc-transitive metacirculants are explored and their connection to the so called tightly attached quartic half-arc-transitive graphs is explored. It is shown that there are three essentially different possibilities for a quartic halfarc-transitive metacirculant which is not tightly attached to exist. These graphs are extensively studied and some infinite families of such graphs are constructed.
124195913
Vertex and Edge Transitive, but not 1-Transitive, Graphs
A (simple, undirected) graph G is vertex transitive if for any two vertices of G there is an automorphism of G that maps one to the other. Similarly, G is edge transitive if for any two edges [a, b] and [c, d] of G there is an automorphism of G such that {c, d} = {f(a), f(b)}. A 1-path of G is an ordered pair (a, b) of (distinct) vertices a and b of G, such that a and b are joined by an edge. G is 1-transitive if for any two 1-paths (a, b) and (c, d) of G there is an automorphism f of G such that c = f(a) and d = f(b). A graph is regular of valency d if each of its vertices is incident with exactly d of its edges.
206078794
A graph which is edge transitive but not arc transitive
A graph having 27 vertices is described, whose automorphism group is transitive on vertices and undirected edges, but not on directed edges.
124892832
VERTEX-PRIMITIVE 1/2-TRANSITIVE GRAPHS
In this paper,we consider the action of group PSL(2,P)(P≡±1(mod 8))on the set of right cosets of a maximal subgroup isomorphic to S4,and survey the nonself-paired orbitals.Then we find many infinite families of vertex-primitve 1/2-transitive graphs.
122754719
Infinite vertex-transitive, edge-transitive non-1-transitive graphs
On montre que tout graphe sommet-transitif, arete-transitif de valence impaire et de croissance sous-exponentielle est 1-transitif. On etend ainsi aux graphes infinis un theoreme de W. T. Tutte pour les graphes finis. On decrit un certain nombre de contre-exemples dans le cas de croissance exponentielle
119585322
Half-transitive graphs of order a product of two distinct primes *
A simple undirected graph X is said to be ½-transitive if the automorphism group AutX of X acts transitively onthe vertices and edges, but not on the arcs of X. In this pape we determine all ½-transitive graphs of order a product of two distinct primes
34567278
Half-Transitive Graphs of Prime-Cube Order
We call an undirected graph X half-transitive if the automorphism group Aut X of X acts transitively on the vertex set and edge set but not on the set of ordered pairs of adjacent vertices of X. In this paper we determine all half-transitive graphs of order p3 and degree 4, where p is an odd prime; namely, we prove that all such graphs are Cayley graphs on the non-Abelian group of order p3 and exponent p2, and up to isomorphism there are exactly (p − 1)/2 such graphs. As a byproduct, this proves the uniqueness of Holt's half-transitive graph with 27 vertices.
17941092
Recent developments in half-transitive graphs
Abstract A vertex-transitive graph is said to be 1 2 -transitive if its automorphism group is vertex- and edge- but not arc-transitive. Some recent results on 1 2 - transitive graphs are given, a few open problems proposed, and possible directions in the research of the structure of these graphs discussed.
11952506
A tetravalent half-arc-transitive graph with non-abelian vertex stabilizer
A construction is given of a 4-valent ½-arc-transitive graph with vertex stabilizer isomorphic to the dihedral group D8. The graph has 10 752 vertices and is the first known example of a 4-valent ½-arc-transitive graph with non-abelian vertex stabilizer.
11482416
Half-arc-transitive graphs and chiral hypermaps
A subgroup G of automorphisms of a graph X is said to be ½-arc-transitive if it is vertex- and edge- but not arc-transitive. The graph X is said to be ½-arc-transitive if Aut X is ½-arc-transitive. The interplay of two different concepts, maps and hypermaps on one side and ½-arc-transitive group actions on graphs on the other, is investigated. The correspondence between regular maps and ½-arc-transitive group actions on graphs of valency 4 given via the well known concept of medial graphs (European J. Combin. 19 (1998) 345) is generalised. Any orientably regular hypermap H gives rise to a uniquely determined medial map whose underlying graph Y admits a ½-arc-transitive group action of the automorphism group G of the original hypermap H. Moreover, the vertex stabiliser of the action of G on Y is cyclic. On the other hand, given graph X and G ≤ Aut X acting ½-arc-transitively with a cyclic vertex stabiliser, we can construct an orientably regular hypermap H with G being the orientation preserving automorphism group. In particularly, if the graph X is ½-arc-transitive, the corresponding hypermap is necessarily chiral, that is, not isomorphic to its mirror image. Note that the associated ½-arc-transitive group action on the medial graph induced by a map always has a stabiliser of order two, while when it is induced by a (pure) hypermap the stabiliser can be cyclic of arbitrarily large order. Hence moving from maps to hypermaps increases our chance of getting different types of ½-arc-transitive group action. Indeed, in last section we have applied general results to construct ½-arc-transitive graphs with cycle stabilisers of arbitrarily large orders.
207208045
Tetravalent half-transitive graphs of order 4p
A graph is half-transitive if its automorphism group acts transitively on its vertex set and edge set, but not on its arc set. In this paper, the tetravalent half-transitive graphs of order 4p are classified for each prime p. It is shown that there are no tetravalent half-transitive Cayley graphs of order 4p and a tetravalent half-transitive non-Cayley graph of order 4p exists if and only if p-1 is divisible by 8, which is unique for a given order.
206571122
On Half-Transitive Metacirculant Graphs of Prime-Power Order
In this paper, infinitely many graphs of large valency which are half-transitive (that is vertex- and edge-transitive but not arc-transitive) are constructed, and a complete classification is given of half-transitive metacirculant graphs of order a p-power and valency less than 2p, where p is a prime. In particular, it is shown that, for any odd prime p, integers n?3 and k?2 such that k divides p?1, there are exactly (pn?2?1)/2+pn?3?1 nonisomorphic connected half-transitive metacirculants of order pn and valency 2k.
121338020
On primitive permutation groups with small suborbits and their orbital graphs
Abstract In this paper, we study finite primitive permutation groups with a small suborbit. Based on the classification result of Quirin [Math. Z. 122 (1971) 267] and Wang [Comm. Algebra 20 (1992) 889], we first produce a precise list of primitive permutation groups with a suborbit of length 4. In particular, we show that there exist no examples of such groups with the point stabiliser of order 2 4 3 6 , clarifying an uncertain question (since 1970s). Then we analyse the orbital graphs of primitive permutation groups with a suborbit of length 3 or of length 4. We obtain a complete classification of vertex-primitive arc-transitive graphs of valency 3 and valency 4, and we prove that there exist no vertex-primitive half-arc-transitive graphs of valency less than 10. Finally, we construct vertex-primitive half-arc-transitive graphs of valency 2 k for infinitely many integers k , with 14 as the smallest valency.
16673585
Constructing 4-valent 1 2 -transitive Graphs with a Nonsolvable Automorphism Group
A graph is said to be 1 2-transitive if its automorphism group is ver-tex and edge but not arc-transitive. For each n 11, a 1 2-transitive graph of valency 4 and girth 6, with the automorphism group isomor-phic to A n Z 2 , is given.
30667786
Half-Transitive Group Actions on Finite Graphs of Valency 4
The action of a subgroupGof automorphisms of a graphXis said to be 12-transitiveif it is vertex- and edge- but not arc-transitive. In this case the graphXis said to be (G, 12)-transitive. In particular,Xis 12-transitiveif it is (AutX, 12)-transitive. The 12-transitive action ofGonXinduces an orientation of the edges ofXwhich is preserved byG. LetXhave valency 4. An even length cycleCinXis aG-alternating cycleif every other vertex ofCis the head and every other vertex ofCis the tail of its two incident edges in the above orientation. It transpires that allG-alternating cycles inXhave the same length and form a decomposition of the edge set ofX(Proposition 2.4); half of this length is denoted byrG(X) and is called theG-radiusofX. Moreover, it is shown that any two adjacentG-alternating cycles ofXintersect in the same number of vertices and that this number, called theG-attachment number aG(X) ofX, divides 2rG(X) (Proposition 2.6). IfXis 12-transitive, we let theradiusand theattachment numberofXbe, respectively, the AutX-radius and the AutX-attachment number ofX. The caseaG(X)=2rG(X) corresponds to the graphXconsisting of twoG-alternating cycles with the same vertex sets and leads to an arc-transitive circulant graph (Proposition 2.4). IfaG(X)=rG(X) we say that the graphXistightly G-attached. In particular, a 12-transitive graphXof valency 4 istightly attachedif it is tightly AutX-attached. A complete classification of tightly attached 12-transitive graphs with odd radius and valency 4 is obtained (Theorem 3.4).
16456389
Quartic half-arc-transitive graphs with large vertex stabilizers
A 12-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. In all previously known constructions of quartic 12-arc-transitive graphs, vertex stabilizers are isomorphic to Z"2,Z"2^2 or to D"8. In this article, for each positive integer m>=1, an infinite family of quartic 12-arc-transitive graphs having vertex stabilizers isomorphic to Z"2^m is constructed.
38469896
Maps and Half-transitive Graphs of Valency 4
A subgroupG of automorphisms of a graphX is said to be 12- transitive if it is vertex- and edge- but not arc-transitive. The graphX is said to be 12-transitive if AutX is 12-transitive. The correspondence between regular maps and 12-transitive group actions on graphs of valency 4 is studied via the well known concept of medial graphs. Among others it is proved that under certain general conditions imposed on a map, its medial graph must be a 12-transitive graph of valency 4 and, vice versa, under certain conditions imposed on the vertex stabilizer, a 12-transitive graph of valency 4 gives rise to\break an irreflexible regular map. This way infinite families of 12-transitive graphs are constructed from known examples of regular maps. Conversely, known constructions of 12-transitive graphs of valency 4 give rise to new examples of irreflexible regular maps. In the end, the concept of a symmetric genus of a 12-transitive graph of valency 4 is introduced. In particular, 12-transitive graphs of valency 4 and small symmetric genuses are discussed.
14193816
Finite graphs of valency 4 and girth 4 admitting half-transitive group actions
Abstract Finite graphs of valency 4 and girth 4 admitting ½-transitive group actions, that is, vertex- and edge- but not arc-transitive group actions, are investigated. A graph is said to be ½-transitive if its automorphism group acts ½-transitively. There is a natural orientation of the edge set of a ½-transitive graph induced and preserved by its automorphism group. It is proved that in a finite ½-transitive graph of valency 4 and girth 4 the set of 4-cycles decomposes the edge set in such a way that either every 4-cycle is alternating or every 4-cycle is directed relative to this orientation. In the latter case vertex stabilizers are isomorphic to Z2.
18001981
Tetravalent Graphs Admitting Half-Transitive Group Actions: Alternating Cycles
In this paper we study finite, connected, 4-valent graphsXwhich admit an action of a groupGwhich is transitive on vertices and edges, but not transitive on the arcs ofX. Such a graphXis said to be (G,1/2)-transitive. The groupGinduces an orientation of the edges ofX, and a certain class of cycles ofX(called alternating cycles) determined by the groupGis identified as having an important influence on the structure ofX. The alternating cycles are those in which consecutive edges have opposite orientations. It is shown thatXis a cover of a finite, connected, 4-valent, (G,1/2)-transitive graph for which the alternating cycles have one of three additional special properties, namely they aretightly attached, loosely attached, orantipodally attached.We give examples with each of these special attachment properties, and moreover we complete the classification (begun in a separate paper by the first author) of the tightly attached examples.
119812934
Half-transitive graphs of valency 4 with prescribed attachment numbers
A graph X is said to be ½-transitive if its automorphism group Aut X acts vertex- and edge-, but not arc-transitively on X. Then Aut X induces an orientation of the edges of X. If X has valency 4, then this orientation gives rise to so-called alternating cycles, that is even length cycles in X whose every other vertex is the head and every other vertex is the tail of its two incident edges in the above orientation. All alternating cycles have the same length 2r(X), where r(X) is the radius of X, and any two adjacent alternating cycles intersect in the same number of vertices, called the attachment number a(X) of X. All known examples of ½-transitive graphs have attachment number 1, r or 2r, where r is the radius of the graph. In this article, we construct ½-transitive graphs with all other possible attachment numbers. The case of attachment number 2 is dealt with in more detail. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 89–99, 2000 
 
The work was done during author's postdoctorship at IMFM, University of Ljubljana.
122911302
Semi-transitive graphs
In this paper, we first consider graphs allowing symmetry groups which act transitively on edges but not on darts (directed edges). We see that there are two ways in which this can happen and we introduce the terms bi-transitive and semi-transitive to describe them. We examine the elementary implications of each condition and consider families of examples; primary among these are the semi-transitive spider-graphs PS(k,N;r) and MPS(k,N;r). We show how a product operation can be used to produce larger graphs of each type from smaller ones. We introduce the alternet of a directed graph. This links the two conditions, for each alternet of a semi-transitive graph (if it has more than one) is a bi-transitive graph. We show how the alternets can be used to understand the structure of a semi-transitive graph, and that the action of the group on the set of alternets can be an interesting structure in its own right. We use alternets to define the attachment number of the graph, and the important special cases of tightly attached and loosely attached graphs. In the case of tightly attached graphs, we show an addressing scheme to describe the graph with coordinates. Finally, we use the addressing scheme to complete the classification of tightly attached semi-transitive graphs of degree 4 begun by Marusic and Praeger. This classification shows that nearly all such graphs are spider-graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 1–27, 2004
37487225
An infinite family of tetravalent half-arc-transitive graphs
A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, a new infinite family of tetravalent half-arc-transitive graphs with girth 4 is constructed, each of which has order 16m such that m>1 is a divisor of 2t^2+2t+1 for a positive integer t and is tightly attached with attachment number 4m. The smallest graph in the family has order 80.
14128355
A CONSTRUCTION FOR VERTEX-TRANSITIVE GRAPHS
1. Introduction. A useful general strategy for the construction of interesting families of vertex-transitive graphs is to begin with some family of transitive permutation groups and to construct for each group T in the family all graphs G whose vertex-set is the orbit V of T and for which T ^ Aut (G), where Aut (G) denotes the automorphism group of G. For example, if we consider the family of cyclic groups ((01.. .n— 1)) generated by cycles (01...»-1) of length n, then the corresponding graphs are the ^-vertex circulant graphs. In this paper we consider transitive permutation groups of degree mn generated by a "rotation" p which is a product of m disjoint cycles of length n and by a "twisted translation" r such that rpr~ l = p a for some a. The abstract groups isomorphic to the groups T = (p, T) are the semi-direct products of two cyclic groups. We call the corresponding graphs metacirculants. We note that similar constructions apply to vertex-transitive digraphs, though we shall restrict our attention here to graphs.
15083399
Lifting Graph Automorphisms by Voltage Assignments
The problem of lifting graph automorphisms along covering projections and the analysis of lifted groups is considered in a purely combinatorial setting. The main tools employed are: (1) a systematic use of the fundamental groupoid; (2) unification of ordinary, relative and permutation voltage constructions into the concept of a voltage space; (3) various kinds of invariance of voltage spaces relative to automorphism groups; and (4) investigation of geometry of the lifted actions by means of transversals over a localization set. Some applications of these results to regular maps on surfaces are given. Because of certain natural applications and greater generality, graphs are allowed to have semiedges. This requires careful re-examination of the whole subject and at the same time leads to simplification and generalization of several known results.
119022126
Connectivity in graphs
a b x u y w v c d Typical question: Is it possible to get from some node u to another node v ? Example: Train network – if there is path from u to v , possible to take train from u to v and vice versa. If it's possible to get from u to v , we say u and v are connected and there is a path between u and v Paths a b x u y w v c d A path between u and v is a sequence of edges that starts at vertex u, moves along adjacent edges, and ends in v. A simple path is a path that does not repeat any edges What are all the simple paths from z to w ? What are all the simple paths from x to y? How many paths (can be non-simple) are there from x to y? Connectedness a b x u y w v c d A graph is connected if there is a path between every pair of vertices in the graph Example: This graph not connected; e.g., no path from x to d A connected component of a graph G is a maximal connected subgraph of G Example Prove: Suppose graph G has exactly two vertices of odd degree, say u and v. Then G contains a path from u to v .