A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary odd girth

A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary odd girth with 2-arc transitive automorphism groups.     

Symmetrical path-cycle covers of a graph and polygonal graphs

A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We introduce a method for constructing near-polygonal graphs with 2-arc transitive automorphism groups. As special cases, we obtain several new infinite families of polygonal graphs.     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

Locally 2‐arc transitive graphs,homogeneous factorizations,and partial linear spaces

We establish natural bijections between three different classes of combinatorial objects; namely certain families of locally 2‐arc transitive graphs, partial linear spaces, and homogeneous factorizations of arc‐transitive graphs. Moreover, the bijections intertwine the actions of the relevant automorphism groups. Thus constructions in any of these areas provide examples for the others. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 139–148, 2006     

Classification of edge‐transitive rose window graphs

Given natural numbers n?3 and 1?a, r?n?1, the rose window graph R_n(a, r) is a quartic graph with vertex set $\{{{x}}_{{i}}|{{i}}\in {\mathbb{Z}}_{{n}}\} \cup \{{{y}}_{{i}}|{{i}}\in{\mathbb{Z}}_{{n}}\}Given natural numbers n?3 and 1?a, r?n?1, the rose window graph R_n(a, r) is a quartic graph with vertex set $\{{{x}}_{{i}}|{{i}}\in {\mathbb{Z}}_{{n}}\} \cup \{{{y}}_{{i}}|{{i}}\in{\mathbb{Z}}_{{n}}\}$ and edge set $\{\{{{x}}_{{i}},{{x}}_{{{i+1}}}\} \mid {{i}}\in {\mathbb{Z}}_n \} \cup \{\{{{y}}_{{{i}}},{{y}}_{{{i+r}}}\}\mid {{i}} \in{\mathbb{Z}}_{{n}}\}\cup \{\{{{x}}_{{{i}}},{{y}}_{{{i}}}\} \mid {{i}}\in {\mathbb{Z}}_{{{n}}}\}\cup \{\{{{x}}_{{{i+a}}},{{y}}_{{{i}}}\} \mid{{i}} \in {\mathbb{Z}}_{{{n}}}\}$. In this article a complete classification of edge‐transitive rose window graphs is given, thus solving one of the three open problems about these graphs posed by Steve Wilson in 2001. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 216–231, 2010     

s‐Regular cubic graphs as coverings of the complete bipartite graph K3,3

A graph is s‐regular if its automorphism group acts freely and transitively on the set of s‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the s‐regular cyclic coverings of the complete bipartite graph K_3,3 for each ≥ 1 whose fibre‐preserving automorphism subgroups act arc‐transitively. As a result, a new infinite family of cubic 1‐regular graphs is constructed. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 101–112, 2004     

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.     

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     

Transitive tournaments and self‐complementary graphs

A simple proof is given for a result of Sali and Simonyi on self‐complementary graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 111–112, 2001     

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     

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     

Large Cayley graphs and vertex‐transitive non‐Cayley graphs of given degree and diameter

For any d?5 and k?3 we construct a family of Cayley graphs of degree d, diameter k, and order at least k((d?3)/3)^k. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide range of sufficiently large degrees and diameters. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 87–98, 2010     

Cubic vertex‐transitive graphs of order 2pq

A graph is vertex?transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1?S and S={s^?1 | s∈S}. The Cayleygraph Cay(G, S) on G with respect to S is defined as the graph with vertex set G and edge set {{g, sg} | g∈G, s∈S}. Feng and Kwak [J Combin Theory B 97 (2007), 627–646; J Austral Math Soc 81 (2006), 153–164] classified all cubic symmetric graphs of order 4p or 2p² and in this article we classify all cubic symmetric graphs of order 2pq, where p and q are distinct odd primes. Furthermore, a classification of all cubic vertex‐transitive non‐Cayley graphs of order 2pq, which were investigated extensively in the literature, is given. As a result, among others, a classification of cubic vertex‐transitive graphs of order 2pq can be deduced. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 285–302, 2010     

A note on some embedding problems for oriented graphs

We conjecture that every oriented graph G on n vertices with δ⁺(G), δ^?(G)≥5n/12 contains the square of a Hamilton cycle. We also give a conjectural bound on the minimum semidegree which ensures a perfect packing of transitive triangles in an oriented graph. A link between Ramsey numbers and perfect packings of transitive tournaments is also considered. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 330–336, 2012     

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).     

Partial characterizations of circular‐arc graphs

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009     

The locally 2-arc transitive graphs admitting an almost simple group of Suzuki type

In this paper, seven families of vertex-intransitive locally (G,2)-arc transitive graphs are constructed, where Sz(q)?G?Aut(Sz(q)), q=²2k+1 for some k∈N. It is then shown that for any graph Γ in one of these families, Sz(q)?Aut(Γ)?Aut(Sz(q)) and that the only locally 2-arc transitive graphs admitting an almost simple group of Suzuki type whose vertices all have valency at least three are (i) graphs in these seven families, (ii) (vertex transitive) 2-arc transitive graphs admitting an almost simple group of Suzuki type, or (iii) double covers of the graphs in (ii). Since the graphs in (ii) have been classified by Fang and Praeger (1999) [6], this completes the classification of locally 2-arc transitive graphs admitting a Suzuki simple group     

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.