Strongly regular Cayley graphs from partitions of subdifference sets of the Singer difference sets

In this paper, we give a new lifting construction of “hyperbolic” type of strongly regular Cayley graphs. Also we give new constructions of strongly regular Cayley graphs over the additive groups of finite fields based on partitions of subdifference sets of the Singer difference sets. Our results unify some recent constructions of strongly regular Cayley graphs related to m-ovoids and i-tight sets in finite geometry. Furthermore, some of the strongly regular Cayley graphs obtained in this paper are new or nonisomorphic to known strongly regular graphs with the same parameters.     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

Generalizing the generalized Petersen graphs

The generalized Petersen graphs (GPGs) which have been invented by Watkins, may serve for perhaps the simplest nontrivial examples of “galactic” graphs, i.e. those with a nice property of having a semiregular automorphism. Some of them are also vertex-transitive or even more highly symmetric, and some are Cayley graphs. In this paper, we study a further extension of the notion of GPGs with the emphasis on the symmetry properties of the newly defined graphs.     

Vertex-transitive graphs that are not Cayley graphs. II

The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph that is not a Cayley graph. In 1983, D. Marus˘ic˘ asked, “For what values of n does there exist such a graph on n vertices?” We give several new constructions of families of vertex-transitive graphs that are not Cayley graphs and complete the proof that, if n is divisible by p² for some prime p, then there is a vertex-transitive graph on n vertices that is not a Cayley graph unless n is p², p³, or 12. © 1996 John Wiley & Sons, Inc.     

On Cayley graphs of rectangular groups

In this paper, we first give a characterization of Cayley graphs of rectangular groups. Then, vertex-transitivity of Cayley graphs of rectangular groups is considered. Further, it is shown that Cayley graphs Cay(S,C) which are automorphism-vertex-transitive, are in fact Cayley graphs of rectangular groups, if the subsemigroup generated by C is an orthodox semigroup. Finally, a characterization of vertex-transitive graphs which are Cayley graphs of finite semigroups is concluded.     

On the Cayley Graphs of Brandt Semigroups

In this article, the Cayley graphs of Brandt semigroups are investigated. The basic structures and properties of this kind of Cayley graphs are given, and a necessary and sufficient condition is given for the components of Cayley graphs of Brandt semigroups to be strongly regular. As an application, the generalized Petersen graph and k-partite graph, which cannot be obtained from the Cayley graphs of groups, can be constructed as a component of the Cayley graphs of Brandt semigroups.     

Finite edge-transitive Cayley graphs and rotary Cayley maps

This paper aims to develop a theory for studying Cayley graphs, especially for those with a high degree of symmetry. The theory consists of analysing several types of basic Cayley graphs (normal, bi-normal, and core-free), and analysing several operations of Cayley graphs (core quotient, normal quotient, and imprimitive quotient). It provides methods for constructing and characterising various combinatorial objects, such as half-transitive graphs, (orientable and non-orientable) regular Cayley maps, vertex-transitive non-Cayley graphs, and permutation groups containing certain regular subgroups.

In particular, a characterisation is given of locally primitive holomorph Cayley graphs, and a classification is given of rotary Cayley maps of simple groups. Also a complete classification is given of primitive permutation groups that contain a regular dihedral subgroup.

     

Almost all Cayley graphs are hamiltonian

It has been conjectured that there is a hamiltonian cycle in every finite connected Cayley graph. In spite of the difficulty in proving this conjecture, we show that almost all Cayley graphs are hamiltonian. That is, as the order n of a groupG approaches infinity, the ratio of the number of hamiltonian Cayley graphs ofG to the total number of Cayley graphs ofG approaches 1.Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University.     

Two sufficient conditions for non-normal Cayley graphs and their applications

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 the full automorphism group of Cay(G, S). In this paper, two sufficient conditions for non-normal Cayley graphs are given and by using the conditions, five infinite families of connected non-normal Cayley graphs are constructed. As an application, all connected non-normal Cayley graphs of valency 5 on A5 are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A5 determined by Xu and Xu. Further, we classify all non-CI Cayley graphs of valency 5 on A5, while Xu et al. have proved that As is a 4-CI group.     

Generalized Cayley graphs of semigroups II

Following Zhu (Semigroup Forum, 2011, doi:), we study generalized Cayley graphs of semigroups. The Cayley D-saturated property, a particular combinatorial property, of generalized Cayley graphs of semigroups is considered and most of the results in Kelarev and Quinn (Semigroup Forum 66:89–96, 2003), Yang and Gao (Semigroup Forum 80:174–180, 2010) are extended. In addition, for some basic graphs and their complete fission graphs, we describe all semigroups whose universal Cayley graphs are isomorphic to these graphs.     

Properties of Groups for the Cage and Degree/Diameter Problems

A (k, g)-cage is a k-regular graph of girth g of minimum order. While many of the best known constructions of small k-regular graphs of girth g are known to be Cayley graphs, no general theory of the relation between the girth of a Cayley graph and the structure of the underlying group has been developed. We attempt to fill the gap by focusing on the girths of Caley graphs of nilpotent and solvable groups, and present a series of results supporting the intuitive idea that the closer a group is to being abelian, the less suitable it is for constructing Cayley graphs of large girths. Specifically, we establish the existence of upper bounds on the girths of Cayley graphs with respect to the nilpotency class and/or the length of the derived sequence of the underlying groups.     

A refined Hurwitz theorem for imbeddings of irredundant Cayley graphs

Hurwitz's theorem states that the order of any finite group acting on a surface of genus γ > 1 is bounded by 168(γ ? 1). It can be refined to give useful information about groups whose order is near this bound. In this paper, similar results are obtained for Cayley graphs imbedded in a surface of genus γ. These results have important implications for the classification of Cayley graphs of low genus and the number of Cayley graphs of a given genus.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

An extended duality theorem and multiplication of several matrices

Motivated by a construction of highly expanding simple Cayley graphs of dihedral groups derived from-or induced by-highly expanding Cayley digraphs fo cyclic groups presented by F. R. K. chung, constructions of simple Cayley graphs on a semidirect product of groups and Cayley digraphs of one of its factors are suggested. In case of the non-normal factor being the cyclic group of order 2. a condition is given to derive spectral bounds of the Cayley graph of the product from those of the Cayley graph of the normal factor.     

Induced cayley graphs and d0ouble covers

Motivated by a construction of highly expanding simple Cayley graphs of dihedral groups derived from-or induced by-highly expanding Cayley digraphs fo cyclic groups presented by F. R. K. chung, constructions of simple Cayley graphs on a semidirect product of groups and Cayley digraphs of one of its factors are suggested. In case of the non-normal factor being the cyclic group of order 2. a condition is given to derive spectral bounds of the Cayley graph of the product from those of the Cayley graph of the normal factor.     

The Cayley graphs of ℤ<Superscript>d</Superscript> and the limits of vertex-primitive graphs of <Emphasis Type="Italic">HA</Emphasis>-type

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ?^d. In this article we prove that for each d > 1 the set of Cayley graphs of ?^d presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ?^d that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ?^d with crystallographic groups.     

Cayley graphs as classifiers for data mining: The influence of asymmetries

The endomorphism monoids of graphs have been actively investigated. They are convenient tools expressing asymmetries of the graphs. One of the most important classes of graphs considered in this framework is that of Cayley graphs. Our paper proposes a new method of using Cayley graphs for classification of data. We give a survey of recent results devoted to the Cayley graphs also involving their endomorphism monoids.     

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

Isomorphisms of Connected Cayley Digraphs

 Let G be a finite group and let Cay() be a Cayley graph of G. The graph Cay() is called a CI-graph of G if, for any for some Aut(G) only when CayCay(). In this paper, we study the isomorphism problem of connected Cayley graphs: to determine the groups G (or the types of Cayley graphs for a given group G) for which all connected Cayley graphs for G are CI-graphs.     

Generalized Cayley graphs of semigroups I

We introduce the concept of generalized Cayley graphs of semigroups and discuss their fundamental properties, and then study a special case, the universal Cayley graphs of semigroups so that some general results are given and the universal Cayley graph of a -partial order of complete graphs with loops is described.