On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

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 Marus?ic? and Praeger. This classification shows that nearly all such graphs are spider‐graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 1–27, 2004     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Constructing cubic edge‐ but not vertex‐transitive graphs

An infinite family of cubic edge‐transitive but not vertex‐transitive graphs with edge stabilizer isomorphic to ℤ₂ is constructed. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 152–160, 2000     

Finite 2‐Distance Transitive Graphs

A noncomplete graph Γ is said to be (G, 2)‐distance transitive if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set of Γ, and for any vertex u of Γ, the stabilizer is transitive on the sets of vertices at distances 1 and 2 from u. This article investigates the family of (G, 2)‐distance transitive graphs that are not (G, 2)‐arc transitive. Our main result is the classification of such graphs of valency not greater than 5. We also prove several results about (G, 2)‐distance transitive, but not (G, 2)‐arc transitive graphs of girth 4.     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Tetravalent vertex‐transitive graphs of order 4p

A graph is vertex‐transitive if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc.     

A class of symmetric graphs with 2‐arc transitive quotients

Let Γ be an X‐symmetric graph admitting an X‐invariant partition ?? on V(Γ) such that Γ_?? is connected and (X, 2)‐arc transitive. A characterization of (Γ, X, ??) was given in [S. Zhou Eur J Comb 23 (2002), 741–760] for the case where |B|>|Γ(C)∩B|=2 for an arc (B, C) of Γ_??.We con‐sider in this article the case where |B|>|Γ(C)∩B|=3, and prove that Γ can be constructed from a 2‐arc transitive graph of valency 4 or 7 unless its connected components are isomorphic to 3 K ₂, C ₆ or K _{3, 3}. As a byproduct, we prove that each connected tetravalent (X, 2)‐transitive graph is either the complete graph K ₅ or a near n‐gonal graph for some n?4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 232–245, 2010     

Stability of arc‐transitive graphs

The present paper investigates arc‐transtive graphs in terms of their stability, and shows, somewhat contrary to expectations, that the property of instability is not as rare as previously thought. Until quite recently, the only known example of a finite, arc‐transitive vertex‐determining unstable graph was the underlying graph of the dodecahedron. This paper illustrates some methods for constructing finite arc‐transitive unstable graphs, and three infinite families of such graphs are given as applications. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 95–110, 2001     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

Vertex‐Transitive Cubic Graphs of Square‐Free Order

A classification of connected vertex‐transitive cubic graphs of square‐free order is provided. It is shown that such graphs are well‐characterized metacirculants (including dihedrants, generalized Petersen graphs, Möbius bands), or Tutte's 8‐cage, or graphs arisen from simple groups PSL(2, p).     

On the Number of 4‐Cycles in a Tournament

If T is an n‐vertex tournament with a given number of 3‐cycles, what can be said about the number of its 4‐cycles? The most interesting range of this problem is where T is assumed to have cyclic triples for some and we seek to minimize the number of 4‐cycles. We conjecture that the (asymptotic) minimizing T is a random blow‐up of a constant‐sized transitive tournament. Using the method of flag algebras, we derive a lower bound that almost matches the conjectured value. We are able to answer the easier problem of maximizing the number of 4‐cycles. These questions can be equivalently stated in terms of transitive subtournaments. Namely, given the number of transitive triples in T, how many transitive quadruples can it have? As far as we know, this is the first study of inducibility in tournaments.     

Regular 4‐critical graphs of even degree

In 1960, Dirac posed the conjecture that r‐connected 4‐critical graphs exist for every r ≥ 3. In 1989, Erd?s conjectured that for every r ≥ 3 there exist r‐regular 4‐critical graphs. In this paper, a technique of constructing r‐regular r‐connected vertex‐transitive 4‐critical graphs for even r ≥ 4 is presented. Such graphs are found for r = 6, 8, 10. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 103–130, 2004     

Locally 3‐Transitive Graphs of Girth 4

A natural topic of algebraic graph theory is the study of vertex transitive graphs. In the present article, we investigate locally 3‐transitive graphs of girth 4. Taking our former results on locally symmetric graphs of girth 4 as a starting point, we show what properties are retained if we weaken the requirement of local symmetry to local 3‐transitivity.     

Realizing finite edge‐transitive orientable maps

J.E. Graver and M.E. Watkins, Memoirs Am. Math. Soc. 126 (601) ( 5 ) established that the automorphism group of an edge‐transitive, locally finite map manifests one of exactly 14 algebraically consistent combinations (called types) of the kinds of stabilizers of its edges, its vertices, its faces, and its Petrie walks. Exactly eight of these types are realized by infinite, locally finite maps in the plane. H.S.M. Coxeter (Regular Polytopes, 2nd ed., McMillan, New York, 1963) had previously observed that the nine finite edge‐transitive planar maps realize three of the eight planar types. In the present work, we show that for each of the 14 types and each integer n ≥ 11 such that n ≡ 3,11 (mod 12), there exist finite, orientable, edge‐transitive maps whose various stabilizers conform to the given type and whose automorphism groups are (abstractly) isomorphic to the symmetric group Sym(n). Exactly seven of these types (not a subset of the planar eight) are shown to admit infinite families of finite, edge‐transitive maps on the torus, and their automorphism groups are determined explicitly. Thus all finite, edge‐transitive toroidal maps are classified according to this schema. Finally, it is shown that exactly one of the 14 types can be realized as an abelian group of an edge‐transitive map, namely, as ?_n × ?₂ where n ≡ 2 (mod 4). © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 1–34, 2001     

Proper path‐factors and interval edge‐coloring of (3,4)‐biregular bigraphs

An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)‐biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)‐biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3‐valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph. © 2009 Wiley Periodicals, Inc. J Graph Theory     

On Finite 2‐Path‐Transitive Graphs

The class of graphs that are 2‐path‐transitive but not 2‐arc‐transitive is investigated. The amalgams for such graphs are determined, and structural information regarding the full automorphism groups is given. It is then proved that a graph is 2‐path‐transitive but not 2‐arc‐transitive if and only if its line graph is half‐arc‐transitive, thus providing a method for constructing new families of half‐arc‐transitive graphs. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 225–237, 2013     

Finite 2‐Geodesic Transitive Graphs of Prime Valency

We classify noncomplete prime valency graphs satisfying the property that their automorphism group is transitive on both the set of arcs and the set of 2‐geodesics. We prove that either Γ is 2‐arc transitive or the valency p satisfies , and for each such prime there is a unique graph with this property: it is a nonbipartite antipodal double cover of the complete graph with automorphism group and diameter 3.     

Small vertex‐transitive and Cayley graphs of girth six and given degree: an algebraic approach

We examine the existing constructions of the smallest known vertex‐transitive graphs of a given degree and girth 6. It turns out that most of these graphs can be described in terms of regular lifts of suitable quotient graphs. A further outcome of our analysis is a precise identification of which of these graphs are Cayley. We also investigate higher level of transitivity of the smallest known vertex‐transitive graphs of a given degree and girth 6 and relate their constructions to near‐difference sets. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:265‐284, 2011