An infinite family of sharply two-arc transitive digraphs

We disclaim Conjecture 1 posed by Seifter in [N. Seifter, Transitive digraphs with more than one end, Discrete Math., to appear], that stated that a connected locally finite digraph with more than one end is either 0-, 1- or highly arc transitive. We describe in this work an infinite family of 2-arc transitive two-ended digraphs, that are not 3-arc transitive.     

Constructing continuum many countable, primitive, unbalanced digraphs

We construct continuum many non-isomorphic countable digraphs which are highly arc transitive, have finite out-valency and infinite in-valency, and whose automorphism groups are primitive.     

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     

Constructing highly arc transitive digraphs using a direct fibre product

We introduce a construction of highly arc transitive digraphs using a direct fibre product. This product generalizes some known classes of highly arc transitive digraphs but also allows us to construct new ones. We use the product to obtain counterexamples to a conjecture advanced by Cameron, Praeger and Wormald on the structure of certain highly arc transitive digraphs.     

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     

Infinite highly arc transitive digraphs and universal covering digraphs

A digraph (that is a directed graph) is said to be highly arc transitive if its automorphism group is transitive on the set ofs-arcs for eachs0. Several new constructions are given of infinite highly arc transitive digraphs. In particular, for a connected, 1-arc transitive, bipartite digraph, a highly arc transitive digraphDL() is constructed and is shown to be a covering digraph for every digraph in a certain classD() of connected digraphs. Moreover, if is locally finite, thenDL() is a universal covering digraph forD(). Further constructions of infinite highly arc transitive digraphs are given.The second author wishes to acknowledge the hospitality of the Mathematical Institute of the University of Oxford, and the University of Auckland, during the period when the research for this paper was doneResearch supported by the Australian Research Council     

kpm阶2-弧传递图

2-弧传递图是对称图类的一个重要的子类,而拟本原和双拟本原的2-弧传递图在2-弧传递图的研究中具有最基本的意义．文中对阶为kp^m（k,p是素数,k≠p,m≥2是整数)的基本2-孤传递图进行了研究。获得了下列结果：(1)kp^m阶G-拟本原的2-弧传递图是几乎单的．(2)对2p^m阶和2^mk阶双拟本原的2-弧传递图的分类进行了刻划,确定了其自同构群的基柱．     

On automorphism groups of quasiprimitive 2-arc transitive graphs

We characterize the automorphism groups of quasiprimitive 2-arc-transitive graphs of twisted wreath product type. This is a partial solution for a problem of Praeger regarding quasiprimitive 2-arc transitive graphs. The solution stimulates several further research problems regarding automorphism groups of edge-transitive Cayley graphs and digraphs. This work forms part of an ARC grant project and is supported by a QEII Fellowship.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2‐connected graphs, that are not 3‐connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2‐connected graphs to k‐connected graphs for any k, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and k‐CS‐transitive 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     

Some sufficient conditions for the existence of kernels in infinite digraphs

A kernel N of a digraph D is an independent set of vertices of D such that for every w∈V(D)−N there exists an arc from w to N. If every induced subdigraph of D has a kernel, D is said to be a kernel perfect digraph. D is called a critical kernel imperfect digraph when D has no kernel but every proper induced subdigraph of D has a kernel. If F is a set of arcs of D, a semikernel modulo F of D is an independent set of vertices S of D such that for every z∈V(D)−S for which there exists an (S,z)-arc of D−F, there also exists an (z,S)-arc in D. In this work we show sufficient conditions for an infinite digraph to be a kernel perfect digraph, in terms of semikernel modulo F. As a consequence it is proved that symmetric infinite digraphs and bipartite infinite digraphs are kernel perfect digraphs. Also we give sufficient conditions for the following classes of infinite digraphs to be kernel perfect digraphs: transitive digraphs, quasi-transitive digraphs, right (or left)-pretransitive digraphs, the union of two right (or left)-pretransitive digraphs, the union of a right-pretransitive digraph with a left-pretransitive digraph, the union of two transitive digraphs, locally semicomplete digraphs and outward locally finite digraphs.     

On finite edge transitive graphs and rotary maps

It is shown that every connected vertex and edge transitive graph has a normal multicover that is a connected normal edge transitive Cayley graph. Moreover, every chiral or regular map has a normal cover that is a balanced chiral or regular Cayley map, respectively. As an application, a new family of half-transitive graphs is constructed as 2-fold covers of a family of 2-arc transitive graphs admitting Suzuki groups.     

Infinite,highly connected digraphs with no two arc-disjoint spanning trees

We present a construction of countably infinite, highly connected graphs and digraphs, which shows that several basic connectivity results on finite graphs, including Edmondsapos;s branching theorem, cannot be extended to the infinite case.     

The Hadwiger number of infinite vertex-transitive graphs

We prove that every infinite, locally finite 3-connected, almost 4-connected, almost transitive, nonplanar graph, which contains infinitely many pairwise disjoint infinite paths belonging to the same end, can be contracted into an infinite complete graph. This implies that every infinite, locally finite, connected, nonplanar vertex-transitive graph with only one end can be contracted into an infinite complete graph. This problem was raised by L. Babai.     

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     

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.     

Geodetic rays and fibers in periodic graphs

Using the notion of fibers, where two rays belong to the same fiber if and only if they lie within bounded Hausdorff‐distance of one another, we study how many fibers of a graph contain a geodetic ray and how many essentially distinct geodetic rays such “geodetic fibers” must contain. A complete answer is provided in the case of locally finite graphs that admit an almost transitive action by some infinite finitely generated, abelian group. Such graphs turn out to have either finitely many or uncountably many geodetic fibers. Furthermore, with finitely many possible exceptions, each of these fibers contains uncountably many geodetic rays. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 67–88, 2000     

Infinite highly connected planar graphs of large girth

We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected.     

Topological groups and recurrence of quasi transitive graphs

We present all steps which are necessary in order to classify all locally finite, infinite graphs which carry a quasi transitive random walk that is recurrent. Some new and/or simpler proofs are given. Most of them rely on the fact that autmomorphism groups of locally finite graphs are locally compact with respect to the topology of pointwise convergence—this allows the use of integration on these groups. Conferenza tenuta il 28 novembre 1994