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     

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.     

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.     

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     

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.     

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     

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     

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

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     

Super-connected edge transitive graphs

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C_n(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected.     

Independent sets and 2‐factors in edge‐chromatic‐critical graphs

In 1968, Vizing made the following two conjectures for graphs which are critical with respect to the chromatic index: (1) every critical graph has a 2‐factor, and (2) every independent vertex set in a critical graph contains at most half of the vertices. We prove both conjectures for critical graphs with many edges, and determine upper bounds for the size of independent vertex sets in those graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 113–118, 2004     

Superconnected and Hyperconnected Small Degree Transitive Graphs

A graph is said to be superconnected if every minimum vertex cut isolates a vertex. A graph is said to be hyperconnected if each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this paper, we characterize superconnected or hyperconnected vertex transitive graphs with degree 4 and 5. As a corollary, superconnected or hyperconnected planar transitive graphs are characterized.     

A compact labeling scheme for series-parallel graphs

A linear time labeling algorithm is presented for series-parallel graphs. The labels enable us to efficiently implement dynamic programming algorithms for sequencing problems with series-parallel precedence constraints. The labeling scheme can also be used to efficiently count and generate the initial sets, terminal sets and independent sets in transitive series-parallel digraphs and to provide a characterization of the maximal independent sets in transitive digraphs.     

Graphs obtained from Moufang loops and regular maps

Using ideas from regular maps, we prove the existence of infinitely many non‐vertex‐transitive Cayley graphs obtained from Moufang loops. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

点可迁图中的正则因子

设图G是一个K-正则连通点可迁图.如果G不是极大限制性边连通的,那么G含有一个(k-1)-因子,它的所有分支都同构于同一个阶价于k和2k-3之间的点可迁图.此结果在某种程度上加强了Watkins的相应命题:如果k正则点可迁图G不是k连通的,那么G有一个因子,它的每一个分支都同构于同一个点可迁图.     

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.     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003     

The action of nilpotent groups on infinite graphs

First we prove a result about the action of nilpotent groups on the set of ends of locally finite graphs. This theorem has immediate consequences for the structure of graphs which allow a transitive action of those groups. Further we investigate the cycle-structure of automorphisms of a transitive nilpotent group and the existence of abelian groups acting on sets of imprimitivity of graphs whose automorphism groups have transitive nilpotent subgroups.     

Vertex‐Transitive Graphs of Prime‐Squared Order Are Hamilton‐Decomposable

We prove that all connected vertex‐transitive graphs of order p², p a prime, can be decomposed into Hamilton cycles.