A combinatorial property and Cayley graphs of semigroups

We describe semigroups satisfying a combinatorial property defined in terms of Cayley 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.     

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.     

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.     

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.     

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 distance-regular Cayley graphs of generalized dicyclic groups

Let G be a generalized dicyclic group with identity 1. An inverse closed subset S of $G?\{1\}$ is called minimal if $〈S〉=G$ and there exists some $s\in S$ such that $〈S?\{s,s^{?1}\}〉\ne G$. In this paper, we characterize distance-regular Cayley graphs $\mathrm{Cay}(G,S)$ of G under the condition that S is minimal.     

A note on Cayley graphs

An example is given of a finite group A of order 144, with a generating set X = {x, y} such that x³ = y² = 1 and such that the Cayley graph C(A, X) has genus 4 and characteristic −6 (both of which are small relative to the order of A), although there is no short relator of the form (xy)^r with r < 12 or of the form [x, y]^r with r < 6. Accordingly this and other possible examples do not fit into a pattern suggested by [5.], 244–268).     

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

Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111: 416–419]. We also generalizes an early result of M. Nánásiová and M. ?koviera [J. Algebraic Combin., 2009, 30: 103–110].     

Integral and distance integral Cayley graphs over generalized dihedral groups

Journal of Algebraic Combinatorics - A graph is said to be integral (resp. distance integral) if all the eigenvalues of its adjacency matrix (resp. distance matrix) are integers. Let H be a finite...     

A note on Hamiltonian decompositions of Cayley graphs

We define a class Γ of 4-regular Cayley graphs on abelian groups and prove every element of Γ to be decomposable into two Hamiltonian cycles. This result is a special case of a conjecture ofB. Alspach and includes a theorem ofJ.-C. Bermond et al. as a subcase.     

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.     

Cayley graphs on abelian groups

Let A be an abelian group and let ι be the automorphism of A defined by: ι: a ? a^?1. A Cayley graph Γ = Cay(A,S) is said to have an automorphism group as small as possible if Aut(Γ)=A?<ι>. In this paper, we show that almost all Cayley graphs on abelian groups have automorphism group as small as possible, proving a conjecture of Babai and Godsil.     

Channel assignment on Cayley graphs

We address various channel assignment problems on the Cayley graphs of certain groups, computing the frequency spans by applying group theoretic techniques. In particular, we show that if G is the Cayley graph of an n‐generated group Γ with a certain kind of presentation, then λ(G;k, 1)≤2(k+n?1). For certain values of k this bound gives the obvious optimal value for any 2n‐regular graph. A large number of groups (for instance, even Artin groups and a number of Baumslag–Solitar groups) satisfy this condition. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 169‐177, 2011