One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

D-saturated property of the Cayley graphs of semigroups

Let D be a finite graph. A semigroup S is said to be Cayley D-saturated with respect to a subset T of S if, for all infinite subsets V of S, there exists a subgraph of Cay(S,T) isomorphic to D with all vertices in V. The purpose of this paper is to characterize the Cayley D-saturated property of a semigroup S with respect to any subset T⊆S. In particular, the Cayley D-saturated property of a semigroup S with respect to any subsemigroup T is characterized.     

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     

On Isomorphisms of Minimal Cayley Graphs and Digraphs

 A Cayley graph or digraph Cay(G,S) is called a CI-graph of G if, for any T⊂G, Cay(G,S)≅Cay(G,T) if and only if S ^σ=T for some σ∈Aut(G). The aim of this paper is to characterize finite abelian groups for which all minimal Cayley graphs and digraphs are CI-graphs. Received: February 13, 1998 Final version received: May 7, 1999     

On normal 2-geodesic transitive Cayley graphs

We investigate connected normal 2-geodesic transitive Cayley graphs Cay(T,S). We first prove that if Cay(T,S) is neither cyclic nor K_4[2], then 〈a〉?{1}??S for all a∈S. Next, as an application, we give a reduction theorem proving that each graph in this family which is neither a complete multipartite graph nor a bipartite 2-arc transitive graph, has a normal quotient that is either a complete graph or a Cayley graph in the family for a characteristically simple group. Finally we classify complete multipartite graphs in the family.     

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.     

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.     

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     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. 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 Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

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.     

On locally primitive Cayley graphs of finite simple groups

In this paper we investigate locally primitive Cayley graphs of finite nonabelian simple groups. First, we prove that, for any valency d for which the Weiss conjecture holds (for example, d?20 or d is a prime number by Conder, Li and Praeger (2000) [1]), there exists a finite list of groups such that if G is a finite nonabelian simple group not in this list, then every locally primitive Cayley graph of valency d on G is normal. Next we construct an infinite family of p-valent non-normal locally primitive Cayley graph of the alternating group for all prime p?5. Finally, we consider locally primitive Cayley graphs of finite simple groups with valency 5 and determine all possible candidates of finite nonabelian simple groups G such that the Cayley graph Cay(G,S) might be non-normal.     

On the Edge-forwarding Indices of Frobenius Graphs

A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay（K, S） for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as （N, R）, is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π（N） of a network （N, R）, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank（G） ≤ 50.     

The non-nilpotent graph of a semigroup

We associate a graph ${\mathcal{N}}_{S}$ with a semigroup S (called the upper non-nilpotent graph of S). The vertices of this graph are the elements of S and two vertices are adjacent if they generate a semigroup that is not nilpotent (in the sense of Malcev). In case S is a group this graph has been introduced by A. Abdollahi and M.?Zarrin and some remarkable properties have been proved. The aim of this paper is to study this graph (and some related graphs, such as the non-commuting graph) and to discover the algebraic structure of S determined by the associated graph. It is shown that if a finite semigroup S has empty upper non-nilpotent graph then S is positively Engel. On the other hand, a semigroup has a complete upper non-nilpotent graph if and only if it is a completely simple semigroup that is a band. One of the main results states that if all connected ${\mathcal{N}}_{S}$ -components of a semigroup S are complete (with at least two elements) then S is a band that is a semilattice of its connected components and, moreover, S is an iterated total ideal extension of its connected components. We also show that some graphs, such as a cycle C _n on n vertices (with n??5), are not the upper non-nilpotent graph of a semigroup. Also, there is precisely one graph on 4 vertices that is not the upper non-nilpotent graph of a semigroup with 4 elements. This work also is a continuation of earlier work by Okni??ski, Riley and the first named author on (Malcev) nilpotent semigroups.     

On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions

Given a finite simple graph G with n vertices, we can construct the Cayley graph on the symmetric group S _n generated by the edges of G, interpreted as transpositions. We show that, if G is complete multipartite, the eigenvalues of the Laplacian of Cay (G) have a simple expression in terms of the irreducible characters of transpositions and of the Littlewood–Richardson coefficients. As a consequence, we can prove that the Laplacians of G and of Cay (G) have the same first nontrivial eigenvalue. This is equivalent to saying that Aldous’s conjecture, asserting that the random walk and the interchange process have the same spectral gap, holds for complete multipartite graphs.     

Sub-semigroups determined by the zero-divisor graph

In this paper we study sub-semigroups of a finite or an infinite zero-divisor semigroup S determined by properties of the zero-divisor graph Γ(S). We use these sub-semigroups to study the correspondence between zero-divisor semigroups and zero-divisor graphs. In particular, we discover a class of sub-semigroups of reduced semigroups and we study properties of sub-semigroups of finite or infinite semilattices with the least element. As an application, we provide a characterization of the graphs which are zero-divisor graphs of Boolean rings. We also study how local property of Γ(S) affects global property of the semigroup S, and we discover some interesting applications. In particular, we find that no finite or infinite two-star graph has a corresponding nil semigroup.     

On Isomorphisms of Finite Cayley Graphs

A Cayley graph Cay(G,S) of a groupGis called a CI-graph if wheneverTis another subset ofGfor which Cay(G,S) Cay(G,T), there exists an automorphism σ ofGsuch thatS^σ = T. For a positive integerm, the groupGis said to have them-CI property if all Cayley graphs ofGof valencymare CI-graphs; further, ifGhas thek-CI property for allk ≤ m, thenGis called anm-CI-group, and a |G|-CI-groupGis called a CI-group. In this paper, we prove that Ais not a 5-CI-group, that SL(2,5) is not a 6-CI-group, and that all finite 6-CI-groups are soluble. Then we show that a nonabelian simple group has the 4-CI property if and only if it is A₅, and that no nonabelian simple group has the 5-CI property. Also we give nine new examples of CI-groups of small order, which were found to be CI-groups with the assistance of a computer.     

Some relations on completely regular semigroups

A semigroup S is called a Clifford semigroup if it is completely regular and inverse. In this paper, some relations related to the least Clifford semigroup congruences on completely regular semigroups are characterized. We give the relation between Y and ξ on completely regular semigroups and get that Y ^* is contained in the least Clifford congruence on completely regular semigroups generally. Further, we consider the relation Y ^*, Y, ν and ε on completely simple semigroups and completely regular semigroups. This work is supported by Leading Academic Discipline Project of Shanghai Normal University, Project Number: DZL803 and General Scientific Research Project of Shanghai Normal University, No. SK200707.     

On Combinatorial Properties of Bands

In this paper we study the D-saturated property of bands defined in terms of their Cayley graphs Cay(S,C), where S is a band and C ? Z(S), the center of S. Also we characterize the Cayley graphs of bands. More generally, for a finite graph Γ =Cay(T, D), where T is a band and D ? Z(T), we give an algorithm for finding all bands S and C ? Z(S) such that Γ =Cay(S, C).     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.