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.     

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.     

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.     

A problem on generalized Cayley graphs of semigroups

Zhu (Semigroup Forum 84(3), 144–156, 2012) investigated some combinatorial properties of generalized Cayley graphs of semigroups. In Remark 3.8 of (Zhu, Semigroup Forum 84(3), 144–156, 2012), Zhu proposed the following question: It may be interesting to characterize semigroups S such that Cay(S,ω _l )=Cay(S,ω _r ). In this short note, we prove that for any regular semigroup S, Cay(S,ω _l )=Cay(S,ω _r ) if and only if S is a Clifford semigroup.     

A combinatorial property and Cayley graphs of semigroups

We describe semigroups satisfying a combinatorial property defined in terms of Cayley graphs.     

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.     

The endomorphism monoids and automorphism groups of Cayley graphs of semigroups

In this note, we introduce the notions of color-permutable automorphisms and color-permutable vertex-transitive Cayley graphs of semigroups. As a main result, for a finite monoid S and a generating set C of S, we explicitly determine the color-permutable automorphism group of \(\mathrm {Cay}(S,C)\) [Theorem 1.1]. Also for a monoid S and a generating set C of S, we explicitly determine the color-preserving automorphism group (endomorphism monoid) of \(\mathrm {Cay}(S,C)\) [Proposition 2.3 and Corollary 2.4]. Then we use these results to characterize when \(\mathrm {Cay}(S,C)\) is color-endomorphism vertex-transitive [Theorem 3.4].     

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.     

Embedding graphs in Cayley graphs

IfY is a finite graph then it is known that every sufficiently large groupG has a Cayley graph containing an induced subgraph isomorphic toY. This raises the question as to what is sufficiently large. Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|³ suffices. Using a form of greedy algorithm we strengthen this to (2 + \sqrt 3 )|Y|^3 $$ " align="middle" border="0"> . Some related results on finite and infinite groups are included.     

Automorphisms of Cayley graphs

The aim of this paper is to characterize subgroups of non-regular automorphism groups of Cayley graphs. Relations between group automorphisms, graph automorphisms and permutations of the edge set of Cayley graphs are investigated.     

Spectra of Cayley graphs

By a result of L. Lovász, the determination of the spectrum of any graph with transitive automorphism group easily reduces to that of some Cayley graph.We derive an expression for the spectrum of the Cayley graph X(G,H) in terms of irreducible characters of the group G:

for any natural number t, where ξ_i is an irreducible character (over $\text{C}$), of degree n_i , and λ_i,1 ,…, λ_i,ni are eigenvalues of X(G, H), each one n_i times. (σn_i² = n = | G | is the total'number of eigenvalues.) Using this formula for t = 1,…, n_i one can obtain a polynomial of degree n_i whose roots are λ_i,1,…,λ_i,ni. The results are formulated for directed graphs with colored edges. We apply the results to dihedral groups and prove the existence of k nonisomorphic Cayley graphs of D_p with the same spectrum provided p > 64k, prime.     

Cayley digraphs and graphs

We shortly recall some definitions that involve refinements of connectivity, and a theorem of Y.O. Hamidoune. We consider some aspects of Cayley digraphs and vertex- and arc-transitive digraphs that he investigated.     

Shifts in Cayley graphs

An automorphism of an undirected simple graph is called a shift if it maps every vertex to an adjacent one. For all finite groups G, we determine the minimum nonzero valency of a Cayley graph on G that does not admit a shift. We also get a classification of groups with all involutions central and such that for every pair a,b of elements of the group, one of ab=ba, aba⁻¹=b⁻¹, bab⁻¹=a⁻¹ or a²=b^±2 holds.     

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.

     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.