On the Cayley graphs of completely simple semigroups

In this paper, the Cayley graphs of completely simple semigroups are investigated. The basic structure and properties of this kind of Cayley graph are given, and a condition is given for a Cayley graph of a completely simple semigroup to be a disjoint union of complete graphs. We also describe all pairs (S,A) such that S is a completely simple semigroup, A⊆S, and Cay (S,A) is a strongly connected bipartite Cayley graph.     

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.     

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

Cayley color graphs of inverse semigroups and groupoids

The notion of Cayley color graphs of groups is generalized to inverse semigroups and groupoids. The set of partial automorphisms of the Cayley color graph of an inverse semigroup or a groupoid is isomorphic to the original inverse semigroup or groupoid. The groupoid of color permuting partial automorphisms of the Cayley color graph of a transitive groupoid is isomorphic to the original groupoid.     

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     

Connected cubic <Emphasis Type="Italic">s</Emphasis>-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two sufficient and necessary conditions for such graphs to be 1- or 2-arcregular are given and based on the conditions, several infinite families of 1- or 2-arc-regular cubic Cayley graphs of alternating groups are constructed. This work was supported by Guangxi Science Foundations (Grant No. 0832054) and Guangxi Postgraduate Education Innovation Research (Grant No. 2008105930701M102)     

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.     

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.     

An explicit characterization of cubic symmetric bi-Cayley graphs on nonabelian simple groups

One of the remarkable contributions in the study of symmetric Cayley graphs on nonabelian simple groups is the complete classification of such graphs that are cubic and nonnormal. This naturally motivates the study of cubic (normal and nonnormal) symmetric bi-Cayley graphs on nonabelian simple groups. In this paper, the full automorphism groups of these graphs are determined, and necessary and sufficient conditions are given for a graph being a cubic normal symmetric Cayley or bi-Cayley graph on a nonabelian simple group (one may then find many examples). As an application, we also prove that cubic symmetric Cayley graphs on nonabelian simple groups are stable.     

Fault Tolerance of Cayley Graphs

It is a difficult problem in general to decide whether a Cayley graph Cay(G; S) is connected where G is an arbitrary finite group and S a subset of G. For example, testing primitivity of an element in a finite field is a special case of this problem but notoriously hard. In this paper, it is shown that if a Cayley graph Cay(G; S) is known to be connected then its fault tolerance can be determined in polynomial time in |S|log(|G|). This is accomplished by establishing a new structural result for Cayley graphs. This result also yields a simple proof of optimal fault tolerance for an infinite class of Cayley graphs, namely exchange graphs. We also use the proof technique for our structural result to give a new proof of a known result on quasiminimal graphs. Received March 10, 2006     

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.     

On Cayley graphs of completely 0-simple semigroups

We give necessary and sufficient conditions for various vertex-transitivity of Cayley graphs of the class of completely 0-simple semigroups and its several subclasses. Moreover, the question when the Cayley graphs of completely 0-simple semigroups are undirected is considered.     

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.     

6度1-正则Cayley图

试图对6度1-正则Cayley图给一个完全分类．利用无核的概念将图自同构群归结到对称群S6的子群．然后根据1-正则图的性质构造出所有可能的具有非交换点稳定子群的无核6度1-正则Cayley图,进一步证明了构造出的图都是有核的,由此给出了这一类图的一个完全分类．     

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.     

Connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two suffcient and necessary conditions for such graphs to be 1- or 2-arc-regular are given and based on the conditions, several infinite families of 1-or 2-arc-regular cubic Cayley graphs of alternating groups are constructed.