Tensor Product of Colour Vertex Transitive Cayley Graphs of Finite Semigroups

www.i-csrs.org

Available free online at http://www.geman.in

Tensor Product of Colour Vertex Transitive Cayley Graphs of Finite Semigroups

A. Assari¹ and N. Hosseinzadeh²

1Department of Basic Science Jundi-Shapur University of Technology

Dezful, Iran

E-mail:[email protected]

2Department of Mathematics Dezful Branch, Islamic Azad University

Dezful, Iran

E-mail:[email protected] (Received: 11-8-13 / Accepted: 15-9-13)

Abstract

It is important to see what kinds of properties of graphs can be transfer to the product of them. Here we will prove that the colour automorphism vertex transitivity can be transfer, and bring a special proof for vertex transitivity property of Cayley graphs of semigroups as well.

Keywords: Cayley graph, semigroup, colour automorphism vertex transi- tive, tensor product, automorphism group

1 Introduction

Let G be a semigroup and S be a nonempty subset of G. The Cayley graph of G relative to S is denoted by Γ = Cay(G, S) is a graph with vertex set G and (x, y) is an edge of Γ if and only if for some s∈S we have y=sx.

The aim of this paper is to prove that the tensor product of two Cayley graphs of semigroups preserves the colour automorphism vertex transitivity condition. Let us first define a few properties of graphs as well as Cayley graphs.

Let Γ₁ = (V₁, E₁) and Γ₂ = (V₂, E₂) be two graphs. Γ = (V, E), the tensor product of them is a graph with vertex setV =V₁×V₂, and ((u₁, u₂),(v₁, v₂))is an edge in Γ if and only if (u1, v1)∈E1 and (u2, v2)∈E2.

An endomorphism of a graph Γ = (V, E) is a mapping φ :V −→V which preserves the edges of Γ. An automorphism of the graph Γ is a on-to-one and onto endomorphism of Γ. We denote the set of all endomorphisms (which is a monoid with the composition operator) and the set of all automorphisms ( which is a group) of Γ by End(Γ) and Aut(Γ) respectively .

A graph Γ = (V, E) is said to be vertex transitive if for any two vertices x, y ∈V, there exists an automorphism of Γ which sendsxtoy. More generally, a subsetXofEnd(Γ) is said to be vertex transitive on Γ and Γ is said to beX- vertex transitive, if for any two verticesx, y ∈V, there exist an endomorphism φ∈X which sends x toy .

Let G be a semigroup and S be a subset of G. An element of φ ∈ End(Cay(G, S)) is called colour preserving endomorphism if sx = y implies s(x^φ) = y^φ for every x, y ∈ G and s ∈ S . Denoted by ColEnd_S(G) and ColAut_S(G) the sets of all colour preserving endomorphisms and colour pre- serving automorphisms of Cay(G, S) respectively. Evidently,

ColAut_S(G)⊂Aut((Cay(G, S)) ColEnd_S(G)⊂End(Cay(G, S))

and ColoAut_S(G) and ColEnd_S(G) are submonoids ofEnd(Cay(G, S)). [3]

A Cayley graph Γ =Cay(G, S) is called colour automorphism vertex tran- sitive if it is ColAut_S(G)-vertex transitive.

We use the notation of [2] for concepts of semigroups. A band is a semigroup entirely consisting of idempotents. A right (left) zero semigroup is a semigroup in which we havexy=y (xy=x) for all elements of the semigroup. A simple semigroupS is a semigroup with no proper ideal (There exists noA⊂S with A 6= S such that SA ⊂ A and AS ⊂ A). By a completely simple semigroup we mean a simple semigroup containing a primitive idempotent.

The Cayley graphs of semigroups is a main consideration in the literature, for example Wang et all in [7] gave necessary and sufficient conditions for various vertex-transitivity of Cayley graphs of the class of completely 0-simple semigroups and its several subclasses. Many large graphs can be constructed by expanding of small graphs, thus it is important to know which properties of small graphs can be transfer to the expanded one, for example Wang in [4] proved that the lexicographic of vertex transitive graphs is also vertex transitive. Michel et all in [5] calculated the distance between two vertices in Cartesian product of two graphs as well as the diameter of the produced graph with respect to the primary graphs and used it to find a condition under that the Cartesian product of two graphs be hyperbolic. It is well known that the

tensor product of two graphs preserves the transitivity condition. Specapan in [6] Found the fewest number of vertices for Cartesian product of two graphs whose removal from the graph results in a disconnected or trivial graph. This motivated us to consider the Tensor product of colour automorphism Cayley graphs of semigroups and prove that this kind of product also preserve the colour automorphism vertex transitivity condition in Cayley graphs of finite semigroups and bring another proof for the vertex transitivity of such graphs as well.

2 Preliminary Notes

The tensor product of Cayley graphs of group is also a Cayley graph [1]. We will show this is also true for the Cayley graphs of semigroups.

Lemma 2.1. Let Γ₁ = Cay(H, S) and Γ₂ = Cay(K, T) be two Cayley graphs of semigroups, then the tensor product of them is also a Cayley graph of semigroups.

Proof. Set Γ = (V, E) the tensor product of Γ₁ and Γ₂. V =H×K is also a semigroup and ((v₁, v₂),(u₁, u₂))∈E if and only if (v₁, u₁) is an edge of Γ₁ and (v₂, u₂) is an edge of Γ₂, i.e there exists∈S andt ∈T such thatu₁ =sv₁ and u₂ = tv₂ and this will happen if and only if (u₁, u₂) = (s, t)(v₁, v₂) for some (s, t)∈ S×T. Thus Γ is a Cayley graph of the semigroup H×T relative to the subset S×T of that.

In [3], the authors provide some sufficient conditions under that a Cayley graph of a semigroup may be vertex transitive or colour automorphism vertex transitive which we bring them here.

Theorem 2.2. Let G be a finite semigroup and S ba a subset of G. Then the Cayley graph Cay(G, S) is colour automorphism vertex transitive if and only if the following conditions hold:

(i) sG =G, for all s∈S;

(ii) < S > is isomorphic to a direct product of a right zero band and a group;

(iiii) |< S > g| is independent of the choice of g ∈G.

Theorem 2.3. Let G be a finite semigroup and S be a subset of G. Then the Cayley graph Cay(G, S) is vertex transitive if and only if the following conditions hold:

(i) sG =G, for all s∈S;

(ii) < S > is a completely simple semigroup;

(iii) the Cayley graph Cay(< S >, S) is vertex transitive;

(iv) |< S > g| is independent of the choice of g ∈G.

3 Main Results

LetH andK be two finite semigroups andS andT be two subsets of them re- spectively. Set Γ₁ =Cay(H, S) and Γ₂ =Cay(K, T) and Γ the tensor product of them. we will show that the colour automorphism vertex transitivity of them can transfer to the tensor product of them as well as the vertex transitivity.

Theorem 3.1. LetΓ₁ and Γ₂ be two colour automorphism vertex transitive Cayley graphs. Then Γ = (V, E) the tensor product of them is also colour automorphism vertex transitive.

Proof. By the definition of tensor product and lemma 2.1 we have Γ =Cay(G, W) where G = H×K and W = S ×T. By theorem 2.2 it is enough to show the three mentioned conditions holds for the semigroup G and its subset W where we know that these conditions hold for the semigroups H and K and their subsetsS and T.

(i) Let w = (s, t) ∈ W = S ×T. By assumptions we have sH = H and tK =K, implying

wG= (s, t)(H×K) =sH×tK =H×K =G

(ii) By assumptions and theorem 2.2 part (ii), we can write < S > and

< T > in the form of B ×M and C×P respectively, where B and C are two right zero bands and M and P are two groups.

Every element of < S > can be written in the form of Πi∈Is_i for some index setI and si ∈S ⊂< S >=B×M and hencesi = (bi, mi) for some b_i ∈ B and m_i ∈ M. B is a right zero band and thus Πi∈Ib_i = b_j for somej ∈I, implying Πi∈Is_i = (b_j,Πi∈Im_i) for someb_j ∈B andm_i ∈M. Therefore we have

B ={b_i|∃s_i ∈S,∃m_i ∈M;s_i = (b_i, m_i)}

and we observe that the cardinality of the set B is not bigger than the cardinality of the set S.

Similarly we can say that

C ={c_i|∃t_i ∈T,∃p_i ∈P;t_i = (c_i, p_i)}

and every element of < T > can be written in the form of Πj∈Jt_j = (c_k,Πj∈Jp_j) where J is an index set and c_k ∈ C for some k ∈ J and pj ∈P for all j ∈J.

Now suppose w ∈< S×T >, thus w= Π_i∈I(s_i, t_i) for some s_i ∈S and t_i ∈T. Since S and T are subsets of < S > and < T > respectively, we can writewby the product of four tuple (b_i, m_i, c_i, p_i) which is isomorphic to the product of four tuple (b_i, c_i, m_i, p_i) fori∈I, b_i ∈B, c_i ∈C, m_i ∈M and p_i ∈P. But B and C are right zero band, implying we can write w in the form (b_k, c_k,Πı∈Im_i,Πi∈Ip_i) for some k ∈I. Implying < S×T >

is a subset of (B ×C)×(M ×P).

Now we want to prove that the converse is also true, i.e. (B×C)×(M×P) is also a subset of < S ×T >. Suppose (b, c, m, p) be an element of (B ×C)×(M ×P). m ∈ M and p ∈ P implying there exists some b_m ∈ B, an index set I, s_i ∈ S∀i ∈ I, c_p ∈ C and an index set J and t_j ∈ P∀j ∈ J such that Πi∈Is_i = (b_m, m) and Πj∈Jt_j = (c_p, p). Since (b,1M)∈< S >= B ×M and (c,1P)∈< T >= C×P and being right zero bandness of B and C, one can deduce Π_j∈J⁺(s_i, t_i) = (b, m, c, p) ∼= (b, c, m, p) for some Index sexJ⁺ which include I and J. Hence we have

< S×T >∼= (B ×C)×(M ×P) where B×C is a right zero band and M ×P is a group.

(iii) By assumption | < S > h| is independent of h ∈ H as well as | <

T > k| relative to k ∈ K. Mapping φ :< S > h →< S > h⁰ for h, h⁰ ∈ H which sends Π_i∈Is_ih to Π_i∈Is_ih⁰ is onto with the condition

| < S > h| = | < S > h⁰| which is finite, implies that φ is a bijection.

Similarly happens for the mapping ψ :< T > k→< T > k⁰ fork, k⁰ ∈K defined by ψ(Π_j∈Jt_jk) = Π_j∈Jt_jk⁰. Implying the mapping (φ, ψ) :<

S ×T > (h, k) →< S ×T > (h⁰, k⁰) which sends Πi∈I(s_i, t_i)(h, k) to Πi∈I(s_i, t_i)(h⁰, k⁰) is a bijection, i.e. |< S×T > (h, k)|is independent of (h, k)∈H×K.

It is a well known that the product of two vertex transitive graphs is also vertex transitive. But we bring an innovative method to proof it for vertex transitive Cayley graphs of semigroups which is a special case of it.

Theorem 3.2. Let Γ₁ and Γ₂ be two vertex transitive Cayley graphs of finite semigroups. Then Γ = (V, E) the tensor product of them is also vertex transitive Cayley graph.

Proof. We bring the notation of theorem 3.1 and by the theorem 2.3 it is sufficient to prove that G satisfies the four conditions in the theorem 2.3.

Conditions (i) and (iv) is proved in the proof of theorem 3.1. Thus is it only to verify the conditions (ii) and (iii).

(ii) By lemma 2.1, we have to show < S ×T > is a completely simple semigroup.

For simplicity of < S ×T >, suppose not and let A be a proper ideal of < S ×T >. Let B = π₁(A) and C = π₂(A) which are ideal of

< S > and < T > respectively, and since A is a proper ideal, at least one of B orC should be a proper ideal of < S > or < T > respectively, which is contradiction to the hypothesis, implying< S×T >is a simple semigroup.

Now by theorem 2.3, < S > has a primitive element such as e₁ and

< T > also has a primitive element such as e₂. one can verify that e = (e1, e2) is a primitive element of < S ×T >.

Thus < S×T > is a completely simple semigroup.

(iii) By theorem 2.3(iii), Γ₁ =Cay(< S >, S) and Γ₂ =Cay(< T >, T) are vertex transitive, thus for two arbitrary vertices of Γ = Cay(< S×T >

, S × T) such as a = (Π_Is_i,Π_It_i) and b = (Π_Js⁰_j,Π_Jt⁰_j), there exists σ ∈ Aut(Γ₁) and δ ∈ Aut(Γ₂) such that σ sends Π_Is_i to Π_Js⁰_j and δ sends Π_It_i to Π_Jt⁰_j. Since (σ, δ)∈Aut(Γ) sendsatob yields Γ is a vertex transitive.

References

[1] A. Assari, Product of normal edge transitive Cayley graphs, (Submitted).

[2] A.H. Clifford and G.B. Preston,The Algebraic Theory of Semigroups (Vol.

I), American Math. Soc, Reprinted with Correction, (1977).

[3] A.V. Kelarev and C.E. Praeger, On transitive Cayley graphs of groups and semigroups, European J. of Com., 24(2003), 59-72.

[4] F. Li, W. Wang, Z. Xu and H. Zhao, Some results on the lexicographic product of vertex-transitive graphs, Applied Math. Letters, 24(2011), 1924-1926.

[5] J. Michel, J.M. Rodriguez, J.M. Sigarreta and M. Villeta, Gromov hy- perbolicity in Cartesian product graphs, Proc. Indian Acad. Sci. (Math.

Sci.), 120(5)(November) (2010), 593-609.

[6] S. Spacapan, Connectivity of Cartesian product of graphs,Applied Math- ematica Letters, 21(7) (2008), 682-685.

[7] Sh. Wang and Y. Li, On Cayley graphs of completely 0-simple semigroups, Central European Journal of Mathematics, 11(5) (2013), 924-930.