Smallest Vertex‐Transitive Graphs of Given Degree and Diameter

For every d and k, we determine the smallest order of a vertex‐transitive graph of degree d and diameter k, and in each such case we show that this order is achieved by a Cayley graph.     

Unitals and Unitary Polarities in Symmetric Designs

We extend the notion of unital as well as unitary polarity from finite projective planes to arbitrary symmetric designs. The existence of unitals in several families of symmetric designs has been proved. It is shown that if a unital in a point-hyperplane design PG _d-1(d,q) exists, then d = 2 or 3; in particular, unitals and ovoids are equivalent in case d = 3. Moreover, unitals have been found in two designs having the same parameters as the PG ₄(5,2), although the latter does not have a unital. It had been not known whether or not a nonclassical design exists, which has a unitary polarity. Fortunately, we have discovered a unitary polarity in a symmetric 2-(45,12,3) design. To a certain extent this example seems to be exceptional for designs with these parameters.     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

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.     

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

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     

Unitals Admitting All Translations

Among all 2‐‐designs, we characterize the Hermitian unitals by the existence of sufficiently many translations. In arbitrary 2‐‐designs, each group of translations with given center acts semiregularly on the set of points different from the center.     

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     

On Cubic Graphs Admitting an Edge-Transitive Solvable Group

Using covering graph techniques, a structural result about connected cubic simple graphs admitting an edge-transitive solvable group of automorphisms is proved. This implies, among other, that every such graph can be obtained from either the 3-dipole Dip₃ or the complete graph K ₄, by a sequence of elementary-abelian covers. Another consequence of the main structural result is that the action of an arc-transitive solvable group on a connected cubic simple graph is at most 3-arc-transitive. As an application, a new infinite family of semisymmetric cubic graphs, arising as regular elementary abelian covering projections of K _3,3, is constructed.     

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.     

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     

正规Cayley图

综述了自１９９０年以来１２－传递图研究的一些新成果,正规Ｃａｙｌｅｙ图的相关结论。     

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     

The Degree‐Diameter Problem for Claw‐Free Graphs and Hypergraphs

We study the degree‐diameter problem for claw‐free graphs and 2‐regular hypergraphs. Let be the largest order of a claw‐free graph of maximum degree Δ and diameter D. We show that , where , for any D and any even . So for claw‐free graphs, the well‐known Moore bound can be strengthened considerably. We further show that for with (mod 4). We also give an upper bound on the order of ‐free graphs of given maximum degree and diameter for . We prove similar results for the hypergraph version of the degree‐diameter problem. The hypergraph Moore bound states that the order of a hypergraph of maximum degree Δ, rank k, and diameter D is at most . For 2‐regular hypergraph of rank and any diameter D, we improve this bound to , where . Our construction of claw‐free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank .     

Augmenting Outerplanar Graphs to Meet Diameter Requirements

Given an undirected graph and an integer , we consider the problem of augmenting G by a minimum set of new edges so that the diameter becomes at most D. It is known that no constant factor approximation algorithms to this problem with an arbitrary graph G can be obtained unless , while the problem with only a few graph classes such as forests is approximable within a constant factor. In this article, we give the first constant factor approximation algorithm to the problem with an outerplanar graph G. We also show that if the target diameter D is even, then the case where G is a partial 2‐tree is also approximable within a constant.     

Two-Arc Transitive Graphs and Twisted Wreath Products

The paper addresses a part of the problem of classifying all 2-arc transitive graphs: namely, that of finding all groups acting 2-arc transitively on finite connected graphs such that there exists a minimal normal subgroup that is nonabelian and regular on vertices. A construction is given for such groups, together with the associated graphs, in terms of the following ingredients: a nonabelian simple group T, a permutation group P acting 2-transitively on a set , and a map F : Tsuch that x = x ^–1 for all x F() and such that Tis generated by F(). Conversely we show that all such groups and graphs arise in this way. Necessary and sufficient conditions are found for the construction to yield groups that are permutation equivalent in their action on the vertices of the associated graphs (which are consequently isomorphic). The different types of groups arising are discussed and various examples given.     

广义Petersen图的宽直径

广义Petersen图是一类重要的并被广泛研究的互连网络。本文证明了广义Petersen图 P(m,2)的直径和3宽直径分别为O(m/4)和O(m/3)。     

Two‐sided Group Digraphs and Graphs

We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets of a group G, we define the two‐sided group digraph to have vertex set G, and an arc from x to y if and only if for some and . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which may be viewed as a simple graph of valency , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.     

广义Petersen图的弱点传递性

图X称为弱点传递图如果X的自同态幺半群EndX在顶点集V(X)上的作用是传递的 .本文给出了广义Petersen图是二分图的充要条件 ,刻划了奇围长小于 9的广义Petersen图的弱点传递性 ,作为推论给出了所有h ≤ 1 5的弱点传递的广义Pe tersen图P(h ,t) .