Bull. Malays. Math. Sci. Soc. DOI 10.1007/s40840-015-0279-x

Isomorphism Conditions for Cayley Graphs of Rectangular Groups Sayan Panma1 · John Meksawang1

Received: 17 March 2014 / Revised: 19 October 2014 © Malaysian Mathematical Sciences Society and Universiti Sains Malaysia 2015

Abstract A rectangular band is defined as a direct product of a left zero semigroup and a right zero semigroup, and a rectangular group is defined as a direct product of a group and a rectangular band. In this paper, we give some equivalent conditions for Cayley graphs of a rectangular group to be isomorphic to each other. Keywords Cayley graph · Digraph · Rectangular band · Right group · Rectangular group Mathematics Subject Classification

05C25 · 08B15 · 20M19 · 20M30

1 Introduction One of the first investigations on Cayley graphs of algebraic structures can be found in Maschke’s theorem from 1896 about groups of genus zero, that is, groups G which possess a generating system A such that the Cayley graph Cay(G, A) is planar, see, for example, [20]. For more results about Cayley graphs of groups, we refer the reader to [3] and [19]. After this, it is natural to investigate Cayley graphs for semigroups which are unions of groups, so-called completely regular semigroups, see, for example, [15]. In [1,16] and [13], Cayley graphs of right(left) groups, rectangular group and

Communicated by Sanming Zhou.

B

John Meksawang [email protected] Sayan Panma [email protected]

1

Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai, Thailand

123

S. Panma, J. Meksawang

finite simple semigroups, respectively, are characterized. Recent studies in a different direction investigate some basic properties of Cayley graphs of ideal in a commutative ring, see [2]. Necessary and sufficient conditions for a Cayley graph of a rectangular group to be isomorphic to a given digraph were given in [16]. In the present paper, we shall give the conditions for two Cayley graphs of a rectangular group to be isomorphic to each other. All sets in this paper are assumed to be finite. An element z of a semigroup S is a left(right) zero of S if zs = z(sz = z) for all s ∈ S. z is a zero of S if it is both a left and right zero of S. A semigroup all of whose elements are left(right) zeros is a left(right) zero semigroup. A direct product of a group and a left(right) zero semigroup is called a left(right) group. A direct product of a left zero and a right zero semigroup is called a rectangular band. A rectangular group is a direct product of a group and a rectangular band. The cardinality of a set X , denoted by |X |, is the number of elements in X . For any nonempty subset A of a semigroups S, let A denote the subsemigroup generated by A in S. Let G be a group and a ∈ G. The order of a is the cardinality of the cyclic subsemigroup {a} and is denoted by or d(a). Let (V1 , E 1 ) and (V2 , E 2 ) be digraphs. A mapping ϕ : V1 → V2 is called a digraph homomorphism if (u, v) ∈ E 1 implies (ϕ(u), ϕ(v)) ∈ E 2 , i.e., ϕ preserves arcs. We write ϕ : (V1 , E 1 ) → (V2 , E 2 ). A digraph homomorphism ϕ : (V, E) → (V, E) is called a digraph endomorphism. If ϕ : (V1 , E 1 ) → (V2 , E 2 ) is a bijective digraph homomorphism and ϕ −1 is also a digraph homomorphism, then ϕ is called a digraph isomorphism. If a digraph isomorphism ϕ : (V1 , E 1 ) → (V2 , E 2 ) exists, then the graphs are called isomorphic and we write (V1 , E 1 ) ∼ = (V2 , E 2 ). A digraph isomorphism ϕ : (V, E) → (V, E) is called a digraph automorphism. ˙ i∈I X i denote the disjoint union of For any family of nonempty set {X i |i ∈ I }, let ∪ Xi , i ∈ I . Let (V1 , E 1 ), (V2 , E 2 ), . . . , (Vn , E n ) be digraphs such that Vi ∩ V j = ∅ for all i = j. The disjoint union of (V1 , E 1 ), (V2 , E 2 ), . . . , (Vn , E n ) is defined as  n   n ˙ n (Vi , E i ) = ∪ ˙ i=1 Vi , ∪˙ i=1 E i . If Vi = V j = V for all i, j, then the edge i=1 n (V , E ) = (V, ∪n E ). sum of (V1 , E 1 ), (V2 , E 2 ), . . . , (Vn , E n ) is defined as ⊕i=1 i i i=1 n Let S be a semigroup and A ⊆ S. We define the Cayley graph Cay(S, A) of S relative to A as follows: S is the vertex set and (u, v), u, v ∈ S, is an arc in Cay(S, A) if there exists an element a ∈ A such that v = ua. The set A is called the connection set of Cay(S, A). A digraph (V, E) is called a semigroup digraph or digraph of a semigroup if there exist a semigroup S and a connection set A ⊆ S such that (V, E) is isomorphic to the Cayley graph Cay(S, A). For any v ∈ V , the number of arcs incident to v is the − → indegree of v and is denoted by d (v). The number of arcs incident from v is called ← − the outdegree of v and is denoted by d (v). Throughout the paper, a graph always means a directed graph without multiple edges, but possibly with loops. A subgraph F of a graph D is called a strong subgraph of D if and only if whenever u and v are vertices of F and (u, v) is an arc in D, then (u, v) is an arc in F as well. If the vertex set of a strong subgraph F is H , then F is said to be induced by H .

123

Isomorphism Conditions for Cayley Graphs of Rectangular…

2 Cayley Graphs of Rectangular Band We consider an isomorphism of Cayley graphs of rectangular bands in this section. From now on, G denotes a group, Rn = {r1 , r2 , . . . , rn } a right zero semigroup, L m = {l1 , l2 , . . . , lm } a left zero semigroup, and pi the projection into the ith component. For any subgroup K of G, G/K denotes the set of all distinct left cosets of K in G. By the definition of right zero semigroups, we get the following lemma. Lemma 2.1 Let A ⊆ Rn , and let v be a vertex in Cay(Rn , A). Then − → (1) d (v) = |Rn | if and only if v ∈ A; − → (2) d (v) = 0 if and only if v ∈ / A. From the above lemma, we have the following lemma. Lemma 2.2 Let A, B ⊆ Rn . Then Cay(Rn , A) ∼ = Cay(Rn , B) if and only if |A| = |B|. It is known that a rectangular band S = L m × Rn is isomorphic to the finite simple semigroup M(G, I, , P), where G = {e} is the trivial group, m = |I | and n = ||. By Theorem 3 in [13], we have the following lemma. Lemma 2.3 Let S = L m × Rn be a rectangular band and A ⊆ S. Then Cay(S, A) is the disjoint union of m isomorphic strong subgraphs Cay({li } × Rn , {li } × p2 (A)) for i ∈ {1, 2, . . . , m}. Theorem 2.4 Let S = L m × Rn be a rectangular band and A, B ⊆ S. Then Cay(S, A) ∼ = Cay(S, B) if and only if | p2 (A)| = | p2 (B)|. Proof (⇒) Let Cay(S, A) ∼ = = Cay(S, B). By Lemma 2.3, we get Cay(S, A) ∼ m m ˙ i=1 Cay({li } × Rn , {li } × p2 (A)) ∼ ˙ i=1 Cay({li } × Rn , {li } × p2 (B)) ∼ ∪ =∪ = Cay(S, B). Then Cay({li } × Rn , {li } × p2 (A)) ∼ = Cay({li } × Rn , {li } × p2 (B)) and thus Cay(Rn , p2 (A)) ∼ = Cay(Rn , p2 (B)). By Lemma 2.2, we get | p2 (A)| = | p2 (B)|. (⇐) Let | p2 (A)| = | p2 (B)|. By Lemma 2.2, we get Cay(Rn , p2 (A)) ∼ = m m ˙ i=1 Cay({li }× Rn , {li }× Cay(Rn , p2 (B)). Then ∪˙ i=1 Cay({li }× Rn , {li }× p2 (A)) ∼ =∪   p2 (B)). By Lemma 2.3, we get Cay(S, A) ∼ = Cay(S, B).

3 Cayley Graphs of Right Groups In this section, we present the conditions for Cayley graphs of a given right group to be isomorphic. By the definition of a right group, we get the two following lemmas. Lemma 3.1 Let S = G × Rn be a right group, A a nonempty subset of S, g, g  ∈ G, and r, r  ∈ Rn . Then the following statements are equivalent: (1) ((g, r ), (g  , r  )) is an arc in Cay(S, A); (2) There exists (a, r  ) ∈ A such that g  = ga; (3) ((g, r  ), (g  , r  )) is an arc in Cay(S, A).

123

S. Panma, J. Meksawang

Lemma 3.2 Let S = G×Rn be a right group, A a nonempty subset of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and (gi  p1 (A) × p2 (A), E i ) a strong subgraph of Cay(S, A) for i = 1, 2, . . . , w. Then (g j  p1 (A) × p2 (A), E j ) and (gk  p1 (A) × p2 (A), E k ) are disjoint strong subgraphs of Cay(S, A) for all j = k. Theorem 3.3 Let S = G × Rn be a right group, A a nonempty subset of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and (gi  p1 (A)× p2 (A), E i ) w ˙ i=1 (gi  p1 (A) × p2 (A), E i ) a subgraph of Cay(S, A). Then Cay(S, A) = ∪ strong w ˙ i=1 (gi  p1 (A)×Rn , E i ), where E i = {((s, t), (u, v)) | t ∈ / p2 (A), ((s, v), (u, v)) ∪ ∈ E i }.  w w ˙ i=1 (gi  p1 (A) × Rn , E i ). It is ˙ i=1 (gi  p1 (A) × p2 (A),E i ) ∪ Proof Let D = ∪ w w ˙ i=1 (gi  p1 (A) × Rn ) = V (D). We ˙ i=1 (gi  p1 (A) × p2 (A)) ∪ clear that S = ∪ will prove that E(Cay(S, A)) = E(D). Let ((g, r ), (g  , r  )) be an arc in Cay(S, A). By Lemma 3.1, there exists (a, r  ) ∈ A and g  = ga. Hence g  ∈ gk1  p1 (A) and g ∈ gk2  p1 (A) for some k1 , k2 ∈ {1, 2, . . . , w}. We have the following cases. w (case 1) If r ∈ p2 (A), then (g, r ), (g  , r  ) ∈ ∪˙ i=1 (gi  p1 (A) × p2 (A)). Since w ˙ i=1 (gi  p1 (A) × p2 (A), E i ) is a strong subgraph of Cay(S, A), ((g, r ), ∪ w (g  , r  )) is an arc in ∪˙ i=1 (gi  p1 (A)× p2 (A), E i ). Therefore ((g, r ), (g  , r  )) is an arc in D. (case 2) If r ∈ / p2 (A), then ((g, r  ), (g  , r  )) is also an arc in Cay(S, A) by Lemma 3.1 and ((g, r ), (g  , r  )) is an arc in Cay(S, A). This implies that ((g, r  ), (g  , r  )) ∈ E i . Then ((g, r ), (g  , r  )) ∈ E i . Hence ((g, r ), (g  , r  )) is an arc in D. Therefore E(Cay(S, A)) ⊆ E(D). To show that E(D) ⊆ E(Cay(S, A)), let ((g, r ), (g  , r  )) be an arc in D. We consider two cases. w (case 1) If ((g, r ), (g  , r  )) is an arc in ∪˙ i=1 (gi  p1 (A) × p2 (A), E i ), then it is an arc w in Cay(S, A) because ∪˙ i=1 (gi  p1 (A) × p2 (A), E i ) is a strong subgraph of Cay(S, A). w (case 2) If ((g, r ), (g  , r  )) is an arc in ∪˙ i=1 (gi  p1 (A) × Rn , E i ), then it is an arc  in E k for some k. We get that ((g, r  ), (g  , r  )) ∈ E k and this implies that ((g, r  ), (g  , r  )) is an arc in Cay(S, A). By Lemma 3.1, we have ((g, r ), (g  , r  )) is also an arc in Cay(S, A). Then E(D) ⊆ E(Cay(S, A)). Hence Cay(S, A) = D.

 

Lemma 3.4 [14] Let S = G × Rn be a right group, and let A be a nonempty subset of S. Then A =  p1 (A) × p2 (A). Theorem 3.5 Let S = G × Rn be a right group, A a nonempty subset of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and (gi  p1 (A)× p2 (A), E i ) a strong subgraph of Cay(S, A). Then (gi  p1 (A) × p2 (A), E i ) ∼ = Cay(A, A) for i = 1, 2, . . . , w. Proof We define f : (gi  p1 (A) × p2 (A), E i ) → Cay(A, A) by (gi a, r ) → (a, r ) for all a ∈  p1 (A) and r ∈ p2 (A). Clearly, f is a bijection. We will prove that f and f −1 are homomorphisms.

123

Isomorphism Conditions for Cayley Graphs of Rectangular…

For (gi a, r ), (gi a  , r  ) ∈ gi  p1 (A) × p2 (A), let ((gi a, r ), (gi a  , r  )) be an arc in (gi  p1 (A) × p2 (A), E i ). Since (gi  p1 (A) × p2 (A), E i ) is a strong subgraph of Cay(S, A), we get that ((gi a, r  ), (gi a  , r  )) is an arc in Cay(S, A). There exists (a  , r  ) ∈ A such that gi a  = gi aa  so a  = aa  . Since f (gi a  , r  ) = (a  , r  ) = (aa  , r  ) = (a, r )(a  , r  ) = f (gi a, r )(a  , r  ), we have ( f (gi a, r ), f (gi a  , r  )) is an arc in Cay(A, A). Therefore f is a homomorphism. Let ( f (gi a, r ), f (gi a  , r  )) be an arc in Cay(A, A). Then there exists (a  , r  ) ∈ A such that f (gi a  , r  ) = f (gi a, r )(a  , r  ). Therefore (a  , r  ) = (a, r )(a  , r  ) = (aa  , r  ), a  = aa  , and r  = r  . Hence (gi a  , r  ) = (gi aa  , r  ) = (gi a, r ) (a  , r  ), so ((gi a, r ), (gi a  , r  )) is an arc in Cay(S, A). Since (gi a, r ), (gi a  , r  ) ∈ gi  p1 (A)× p2 (A) and (gi  p1 (A) × p2 (A), E i ) is a strong subgraph of Cay(S, A), we thus get ((gi a, r ), (gi a  , r  )) is an arc in (gi  p1 (A) × p2 (A), E i ). Therefore f −1 is a homo  morphism. This means that (gi  p1 (A) × p2 (A), E i ) ∼ = Cay(A, A). Lemma 3.6 Let S = G×Rn be a right group, A a nonempty subset of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and (gi  p1 (A) × p2 (A), E i ) a strong sub− → graph of Cay(S, A). Then for all v ∈ V (Cay(S, A)), d (v) = 0 if and only if w ˙ i=1 gi  p1 (A) × p2 (A). v∈∪ − → Proof (⇒) Let v = (h 1 , r1 ) ∈ S and d (v) = 0. Then there exists u = (h 2 , r2 ) ∈ S such that (u, v) is an arc in Cay(S, A). Hence there exists a = (g  , r  ) ∈ A such that v = ua. Therefore (h 1 , r1 ) = (h 2 , r2 )(g  , r  ) = (h2 g  , r  ), which implies that w r1 = r  ∈ p2 (A). Since h 1 ∈ G = ∪˙ i=1 gi  p1 (A) , we have v = (h 1 , r1 ) ∈   w ˙ i=1 gi  p1 (A) × p2 (A). ∪  w  ˙ i=1 gi  p1 (A) × p2 (A). We get that h 1 ∈ G and (⇐) Let v = (h 1 , r ) ∈ ∪ r ∈ p2 (A). We need consider the two cases. (case 1) If v ∈ A, there exists (e, r ) ∈ S, where e is the identity of G. Since (e, r )(h 1 , r ) = (eh 1 , r ) = (h 1 , r ) = v, there is an arc from (e, r ) to v. − → Therefore d (v) = 0. (case 2) If v ∈ / A, then there exists (h 2 , r ) ∈ A for some h 2 ∈ G. Because G is a group −1 and h 1 , h 2 ∈ G, this implies that h −1 2 ∈ G and h 1 h 2 ∈ G. Then we have −1 −1 −1 (h 1 h 2 , r ) ∈ S. Since (h 1 h 2 , r )(h 2 , r ) = (h 1 h 2 h 2 , r ) = (h 1 , r ) = v, − → there exists an arc from (h 1 h −1 2 , r ) to v. Therefore d (v) = 0.   A path from a vertex u 0 to some vertex u n in a graph (V, E) is a sequence of vertices u 0 , u 1 , u 2 , . . . , u n , where (u i−1 , u i ) for all i, is an arc in (V, E). If (u i−1 , u i ) or (u i , u i−1 ) is an arc in (V, E), then we say that there is semipath between u 0 and u n . A graph (V, E) is connected if there is a semipath between any two vertices. The following lemmas will be used in the proof of Theorem 3.14. Lemma 3.7 Let S = G×Rn be a right group, A a nonempty subset of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and (gi  p1 (A) × p2 (A), E i ) a strong subgraph of Cay(S, A). Then for any i ∈ {1, 2, . . . , w}, (gi  p1 (A) × p2 (A), E i ) is connected.

123

S. Panma, J. Meksawang

  Proof Let (gi x, β), (gi y, γ ) ∈ gi  p1 (A) × p2 (A) . Then (x, β), (y, γ ) ∈  p1 (A) × p2 (A) = A. There are   a1 , a2 , . . . , aq ∈ A such that (y, γ ) = (x, β)a1 a2 . . . aq for some q ≤  A. Hence (gi y, γ ) = (gi x, β)a1 a2 . . . aq . This means that there   is an arc from (gi x, β)a  1 a2 .. . aq−1 to (gi y, γ ). Since  (gi x, β), (gi x,β)a1 , (gi x, β)a1 , (gi x, β)a1 a2 , . . . , (gi x, β)a1 a2 . . . aq−2 , (gi x, β)a1 a2 . . . aq−1 are arcs in Cay(S, A), there is a path (gi x, β), (gi x, β)a1 , (gi x, β) a1 a2 , . . . , (gi x, β)a1 a2 . . . aq−1 , (gi y, γ ) in Cay(S, A). We conclude that (gi  p1 (A)   × p2 (A), E i ) is connected. Since a strong subgraph (gi  p1 (A)× p2 (A), E i ) is connected, we have (gi  p1 (A)× p2 (A), E i ) ∪ (gi  p1 (A) × Rn , E i ) is also connected for any i ∈ {1, 2, . . . , w}, where E  is defined as in Theorem 3.3. Lemma 3.8 Let S = G × Rn be a right group, A and B be nonempty subsets (B) = of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and G/ p1  w w ˙ i=1 ˙ i=1 ∪ (gi  p1 (A)  × p2 (A), E i ) {h 1  p1 (B), h 2  p1 (B), . . . , h z  p1 (B)}. If ∪ z z  ˙ j=1 (h j  p1 (B) × p2 (B), E j ) ∪˙ j=1 (h j  p1 (B) × (gi  p1 (A) × Rn , E i ) ∼ = ∪ Rn , E j ), then w = z and (gi  p1 (A) × p2 (A), E i ) ∼ = (h j  p1 (B) × p2 (B), E j ) for all i, j.  w w z ˙ i=1 (gi  p1 (A)×Rn , E i ) ∼ Proof Let ∪˙ i=1 (gi  p1 (A)× p2 (A), E i ) ∪ = ∪˙ j=1 (h j  p1  z ˙ j=1 (h j  p1 (B) × Rn , E j ). Then there exists an isomor(B) × p2 (B), E j ) ∪  w w ˙ (gi  p1 (A)× p2 (A)) ∪˙ i=1 ˙ zj=1 (h j  p1 (B)× phism f : ∪ (gi  p1 (A)× Rn ) → ∪   i=1 w  ˙ zj=1 (h j  p1 (B) × Rn ). By Lemma 3.6, we get that |∪ ˙ i=1 gi  p1 (A) × p2 (B)) ∪     w ˙ zj=1 h j  p1 (B) × p2 (B)| and we have f (∪ ˙ i=1 p2 (A)| = |∪ gi  p1 (A) × p2 (A)) =   z ˙ j=1 h j  p1 (B) × p2 (B). Since f is an isomorphism, we thus get the restriction of ∪  w  w ˙ i=1 ˙ i=1 (gi  p1 (A)× p2 (A), E i ) gi  p1 (A) × p2 (A) is an isomorphism from ∪ f to ∪ z w ˙ ˙ to ∪ j=1 (h j  p1 (B) × p2 (B), E j ). Therefore ∪i=1 (gi  p1 (A) × p2 (A), E i ) ∼ = ˙ zj=1 (h j  p1 (B) × p2 (B), E j ). In view of Theorem 3.5 and Lemma 3.7, we get ∪   that w = z and (gi  p1 (A) × p2 (A), E i ) ∼ = (h j  p1 (B) × p2 (B), E j ). Lemma 3.9 Let S = G × Rn be a right  group, A and B nonempty subsets of S. If Cay(S, A) ∼ = Cay(S, B), then  p2 (A) =  p2 (B). Proof Let G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)} and G/ p1 (B) = ∼ {h 1  p1 (B), h 2  p1 (B), . . . , h z  p1 (B)}. Assume that  w Cay(S, A) = Cay(S, B).  ˙ By 3.8, we get that ∪i=1 gi  p1 (A) × p2 (A) =  w Theorem 3.3 and Lemma  w ∪ ˙ j=1 h j  p1 (B) × p2 (B) for all gi , h j ∈ G. Since ∪˙ i=1 gi  p1 (A) = G =         ˙ wj=1 h j  p1 (B), we have G × p2 (A) = G × p2 (B). Therefore G  ×  p2 (A) = ∪         G  ×  p2 (B). Hence  p2 (A) =  p2 (B).   By Theorem 4 in [13], we have the next lemma. Lemma 3.10 Let S = G × Rn be right group, and let (g, λ), (h, β) ∈ S, where g, h ∈ G and λ, β ∈ Rn . Then Cay(S, {(g, λ)}) ∼ = Cay(S, {(h, β)}) if and only if or d(g) = or d(h).

123

Isomorphism Conditions for Cayley Graphs of Rectangular…

Theorem 3.11 Let S = G × Rn be a right group,  A and B nonempty subsets of S. Let Ar =  p1 (A)×{r }, Aˆ r = A∩ Ar and Aˆ = { Aˆ r r ∈ p2 (A)}. Br , Bˆ r and Bˆ are defined         similarly. If Cay(A, A) ∼ = Cay(B, B), then  Aˆ  =  Bˆ  and  p1 (A) =  p1 (B).     Proof Let Cay(A, A) ∼ = Cay(B, B). By Lemma 3.9,  p2 (A) =  p2 (B) and         then  Aˆ  =  Bˆ . Since Cay(A, A) ∼ = Cay(B, B) , we get that A = B. By Lemma 3.4,    p1 (A) × p2 (A) =      p1 (A) ×  p2 (A) =    p1 (A) =

   p1 (B) × p2 (B);      p1 (B) ×  p2 (B);    p1 (B).  

Theorem 3.12 Let S = G × Rn be a right group, Aand B nonempty subsets of S. Let Ar =  p1 (A) × {r }, Aˆ r = A ∩ Ar and Aˆ = { Aˆ r r ∈ p2 (A)}. Br , Bˆ r and Bˆ are defined similarly. Then Cay(A, A) ∼ = Cay(B, B) if the following conditions hold:         (1)  Aˆ  =  Bˆ  and  p1 (A) =  p1 (B);     ˆ (2) There exists a bijection f : Aˆ → Bˆ such that  Aˆ r  =  f ( Aˆ r ) for all Aˆ r ∈ A; ˆ there exists a bijection ϕr : Aˆ r → f ( Aˆ r ) such that (3) For each Aˆ r ∈ A, or d( p1 (a)) = or d( p1 (ϕr (a))) for all a ∈ Aˆ r .     Proof By (1), A = B. By Lemma 3.10 and (3), we get that Cay(A, {a}) ∼ = Cay(B, {ϕr (a)}) for all a ∈ Aˆ r . Then Cay(A, Aˆ r ) = ⊕a∈ Aˆ r Cay(A, {a}) ∼ = ⊕a∈ Aˆ r Cay(B, {ϕr (a)}) = Cay(B, ϕr ( Aˆ r )). ˆ Then By (2), Cay(A, Aˆ r ) ∼ = Cay(B, f ( Aˆ r )) for all Aˆ r ∈ A.   ⊕ Aˆ r ∈ Aˆ Cay A, Aˆ r   Cay A, ∪ Aˆ r ∈ Aˆ Aˆ r   Cay A, A

  ∼ = ⊕ Aˆ r ∈ Aˆ Cay B, f ( Aˆ r ) ;   ∼ = Cay B, ∪ Aˆ r ∈ Aˆ f ( Aˆ r ) ;   ∼ = Cay B, B .  

Lemma 3.13 Let S = G × Rn be a right group, A a nonempty subset of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and (gi  p1 (A)× p2 (A), E i ) ˙w a strong subgraph  w of Cay(S, A). Then for every i ∈w{1,2, . . . , w}, ∪i=1 (gi  p1 (A) × ˙ i=1 (gi  p1 (A) × Rn , E i ) = ∪ ˙ i=1 (gi  p1 (A) × p2 (A), E i ) ∪ p2 (A), E i ) ∪  (gi  p1 (A) × Rn , E i ) , where E  is defined as in Theorem 3.3. Theorem 3.14 Let S = G × Rn be a right group, A and B be nonempty subsets of S. Then Cay(S, A) ∼ = Cay(B, B). = Cay(S, B) if and only if Cay(A, A) ∼ Proof Let G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)} and G/ p1 (B) = {h 1  p1 (B), h 2  p1 (B), . . . , h z  p1 (B)}.

123

S. Panma, J. Meksawang

(⇒) Let Cay(S, A) ∼ = Cay(S, B). Then there exists an isomorphism f : Cay(S,  wA) w ˙ i=1 ˙ i=1 (gi  p1 (A) × p2 (A), E i ) ∪ → Cay(S, B). By Theorem 3.3, we get that ∪ ˙ zj=1 (h j  p1 (B)×Rn , E j ). ˙ zj=1 (h j  p1 (B)× p2 (B), E j ) ∪ (gi  p1 (A)×Rn , E i ) ∼ =∪ In view of Lemma 3.8, (gi  p1 (A) × p2 (A), E i ) ∼ = (h j  p1 (B) × p2 (B), E j ). By Theorem 3.5, we get Cay(A, A) ∼ = Cay(B, B).     (⇐) Let Cay(A, A) ∼ = Cay(B, B). By Lemma 3.12,  p1 (A) =  p1 (B) and thus w = |G|/| p1 (A)| = |G|/| p1 (B)| = z. By Theorem 3.5, we get (gi  p1 (A) × p2 (A), E i ) ∼ = (h j  p1 (B) × p2 (B), E j ) for all i, j ∈ {1, 2, . . . , w}. It w z ˙ i=1 (gi  p1 (A) × p2 (A), E i ) ∼ follows that ∪ = ∪˙ j=1 (h j  p1 (B) × p2 (B), E j ). There w ˙ i=1 (gi  p1 (A) × p2 (A), E i ) → ∪ ˙ zj=1 (h j  p1 (B) × exists an isomorphism f : ∪ w ˙ i=1 ˙ z (h  p (B) × p2 (B)|. p2 (B), E j ). Therefore |∪ (gi  p1 (A) × p2 (A)| = |∪  j=1 j  1   w z ˙ i=1 gi  p1 (A) = G = ∪ ˙ j=1 h j  p1 (B), then G × p2 (A) = G × p2 (B). Since ∪             Hence G  ×  p2 (A) = G  ×  p2 (B) and thus  p2 (A) =  p2 (B). Suppose that Rn \ p2 (A) = {q1 , q2 , . . . , qm } and Rn \ p2 (B) = {q1 , q2 , . . . , qm }. Let w w ˙ i=1 ˙ i=1 (gi  p1 (A)× p2 (A), E i ) ∪ (gi  p1 (A)× Rn , E i ) → r ∈ p2 (A). Define T : ∪  z z ˙ j=1 (h j  p1 (B) × p2 (B), E j ) ∪˙ j=1 (h j  p1 (B) × Rn , E j ) by ∪  T (s, rl ) =

if rl ∈ p2 (A) f (s, rl ) ( p1 ( f (s, r )), qk ) if rl = qk for some qk ∈ Rn \ p2 (A).

Clearly, T is well defined and is surjective. To show T is injective, let x1 = (u 1 , λ1 ), x2 = (u 2 , λ2 ) ∈ S and T (x1 ) = T (x2 ). We need to consider the following two cases: (case 1) If λ1 , λ2 ∈ p2 (A), then T (x1 ) = f (x1 ) and T (x2 ) = f (x2 ). Since T (x1 ) = T (x2 ), we have f (x1 ) = f (x2 ) and x1 = x2 because f is a graph isomorphism. / p2 (A), assume that λ1 = ql and λ2 = qk . Thus T (x1 ) = (case 2) If λ1 , λ2 ∈ ( p1 ( f (u 1 , r )), ql ) and T (x2 ) = ( p1 ( f (u 2 , r )), qk ). Since T (x1 ) = T (x2 ), we have ( p1 ( f (u 1 , r )), ql ) = ( p1 ( f (u 2 , r )), qk ). It follows that ql = qk and p1 ( f (u 1 , r )) = p1 ( f (u 2 , r )). Hence by the definition of T , λ1 = λ2 . Since f is a graph isomorphism, we have u 1 = u 2 . Therefore x1 = x2 . By the above two cases, we conclude that T is an injection. We will prove that T and T −1 are homomorphisms.  w w ˙ i=1 Assume that ((x, rc ), (y, rd )) is an arc in ∪˙ i=1 (gi  p1 (A) × p2 (A), E i ) ∪ (gi  p1 (A) × Rn , E i ). Thus (y, rd ) = (x, rc )(a, rt ) for some (a, rt ) ∈ A. Hence (y, rd ) = (xa, rt ) and thus rd = rt ∈ p2 (A) and y = xa. We have the following two cases.     (case 1) rc ∈ p2 (A). Then T (x, rc ), T (y, rd ) = f (x, rc ), f (y, rd ) is an arc in  z ˙ j=1 (h j  p1 (B) × Rn , E j ) since f is an ˙ zj=1 (h j  p1 (B) × p2 (B), E j ) ∪ ∪ isomorphism. (case 2) rc ∈ Rn \ p2 (A). Then rc = qk for some k ∈ {1, 2, . . . , m}. Hence w ˙ i=1 (gi  p1 (A)×Rn , E i ). Then ((x, rd ), (y, rd )) ((x, rc ), (y, rd )) is an arc in ∪ w ˙ is an arc in ∪i=1 (gi  p1 (A) × p2 (A), E i ). By Lemma 3.1, ((x, r ), (y, rd )) is w also an arc in ∪˙ i=1 (gi  p1 (A)× p2 (A), E i ). It follows that ( f (x, r ), f (y, rd ))

123

Isomorphism Conditions for Cayley Graphs of Rectangular…

˙ zj=1 (h j  p1 (B) × p2 (B), E j ). Let f (x, r ) = (x  , r  ) and is an arc in ∪   z f (y, rd ) = (y  , rd ). Therefore (x  , r  ), (y  , rd ) is an arc in ∪˙ j=1 (h j  p1 (B)     ˙ zj=1 (h j  p1 (B)× × p2 (B), E j ) and thus (x , rd ), (y  , rd ) is also an arc in ∪   ˙ zj=1 (h j  p1 (B) × p2 (B), E j ). Therefore ((x  , qk ), (y  , rd )) is an arc in ∪   Rn , E j ). This means that ((x  , qk ), (y  , rd )) = ( p1 ( f (x, r )), qk ), (y  , rd ) z = (T (x, rc ), T (y, rd )) is an arc in ∪˙ j=1 (h j  p1 (B) × Rn , E j ). Hence  z ˙ j=1 (h j ˙ zj=1 (h j  p1 (B) × p2 (B), E j ) ∪ (T (x, rc ), T (y, rd )) is an arc in ∪  p1 (B) × Rn , E j ). Thus T is a homomorphism.  z ˙ zj=1 (h j  p1 (B)× p2 (B), E j ) ∪ ˙ j=1 Assume that (T (x, rc ), T (y, rd )) is an arc in ∪  (h j  p1 (B) × Rn , E j ). We have the following two cases. ˙ zj=1 (h j  p1 (B) × p2 (B), E j ), then (case 1) If (T (x, rc ), T (y, rd )) is an arc in ∪ we get that T (x, rc ) = f (x, rc ) and T (y, rd ) = f (y, rd ). Therez fore ( f (x, rc ), f (y, rd )) is an arc in ∪˙ j=1 (h j  p1 (B) × p2 (B), E j ). w ˙ i=1 (gi  p1 (A) × p2 (A), E i ) to Since f is a graph isomorphism from ∪ z ˙ ∪ j=1 (h j  p1 (B) × p2 (B), E j ), we get that ((x, rc ), (y, rd )) is an arc in w ˙ ˙ i=1 (gi  p1 (A) ∪  w× p2 (A), E i ) and it is also an arc in ∪i=1 (gi  p1 (A) × ˙ i=1 (gi  p1 (A) × Rn , E i ). p2 (A), E i ) ∪ (case 2) Suppose that (T (x, rc ), T (y, rd )) is an arc in ∪˙ j=1 (h j  p1 (B) × Rn , E j ). Then rc = qk for some k ∈ {1, 2, . . . , m}. Let T (y, rd ) = f (y, rd ) = ˙ zj=1 (h j  p1 (B) × (y  , rd ). Then (( p1 ( f (x, r )), qk ), (y  , rd )) is an arc in ∪ ˙ zj=1 (h j  p1 (B) × Rn , E j ) and so (( p1 ( f (x, r )), rd ), (y  , rd )) is an arc in ∪ p2 (B), E j ). Hence there exists (b, rd ) ∈ B such that (y  , rd ) = ( p1 ( f (x, r )), rd )(b, rd ). Let f (x, r ) = f (x  , r  ). Then f (y, rd ) = (x  , rd )(b, rd ) = (x  b, rd ) = (x  , r  )(b, rd ) = f (x, r ) (b, rd ). This means that ( f (x, r ), f (y, z rd )) is an arc in ∪˙ j=1 (h j  p1 (B) × p2 (B), E j ). Then ((x, r ), (y, rd )) is w ˙ i=1 (gi  p1 (A) × p2 (A), E i ). Therefore ((x, rc ), (y, rd )) is an an arc in ∪ w  ˙w ˙ arc in ∪i=1 (g i  pw1 (A) × Rn , E i ) and it  is also an arc in ∪i=1 (gi  p1 (A) × ˙ i=1 (gi  p1 (A) × Rn , E i ). p2 (A), E i ) ∪  w w ˙ i=1 (g j ˙ i=1 Thus T −1 is a homomorphism. Hence ∪ (gi  p1 (A) × p2 (A), E i ) ∪ z z  ∼ ˙ ˙  p1 (A) × Rn , E i ) = ∪ j∈I (h j  p1 (B) × p2 (B), E j ) ∪ j=1 (h j  p1 (B) × Rn , E j ).   By Theorem 3.3, we have Cay(S, A) ∼ = Cay(S, B). z

Example 1 Let S = S3 × R2 be a right group, where S3 = {(1), σ, σ 2 , τ, τ σ 2 , τ σ } is the symmetric group with (1) an identity, σ = (123), σ 2 = (132), τ = (12), τ σ 2 = (13), τ σ = (23). Let A = {((1), r1 ), (τ, r1 ), (τ, r2 )} and B = {(τ σ, r1 ), ((1), r2 ), (τ σ, r2 )}. It is easily seen that Cay(S, A) ∼ = Cay(S, B) (see Figs. 1 and 2). We have Aˆ r1 = {((1), r1 ), (τ, r1 )}, Aˆ r2 = {(τ, r2 )}, Bˆ r1 = {(τ σ, r1 )}, and Bˆ r2 = ˆ = | B|. ˆ {((1), r2 ), (τ σ, r2 )}. Therefore Aˆ = { Aˆ r1 , Aˆ r2 }, Bˆ = { Bˆ r1 , Bˆ r2 }, and thus | A| Since  p1 (A) = {e, τ } and  p1 (B) = {e, τ σ }, then | p1 (A)| = | p1 (B)|.

123

S. Panma, J. Meksawang Fig. 1 Cay(S, A)

((1), r2 )

((1), r1 )

(τ, r2 )

(τ, r1 )

(τ σ 2 , r2 )

(τ σ 2 , r1 )

(σ, r2 )

(σ, r1 )

(σ 2 , r2 )

(σ 2 , r1 )

(τ σ, r2 )

(τ σ, r1 )

We thus get | Aˆ r1 | = 2 = | Bˆ r2 | and | Aˆ r2 | = 1 = | Bˆ r1 |. There exists a bijective function f from Aˆ to Bˆ such that f ( Aˆ r1 ) = Bˆ r2 and f ( Aˆ r2 ) = Bˆ r1 . Moreover, there are bijective functions ϕr1 : Aˆ r1 → Bˆ r2 such that

ϕr1 ((1), r1 ) = ((1), r2 ) ϕr1 (τ, r1 ) = (τ σ, r2 )

and

ϕr2 : Aˆ r2 → Bˆ r1 such that

ϕr2 (τ, r2 ) = (τ σ, r1 )

such that or d( p1 (a)) = or d( p1 (ϕr1 (a))) and or d( p1 (b)) = or d( p1 (ϕr2 (b))) for all a ∈ Aˆ r1 and b ∈ Aˆ r2 . According to Theorem 3.12, Cay(A, A) ∼ = Cay(B, B).

4 Cayley Graphs of Rectangular Groups By Theorem 4 in [13], we have the following theorem, which presents an equivalent condition for two Cayley graphs of a given rectangular group relative to one-element subsets are isomorphic to each other.

123

Isomorphism Conditions for Cayley Graphs of Rectangular… Fig. 2 Cay(S, B)

(τ σ 2 , r2 )

(τ σ 2 , r1 )

(σ 2 , r2 )

(σ 2 , r1 )

((1), r2 )

((1), r1 )

(τ σ, r2 )

(τ σ, r1 )

(τ, r2 )

(τ, r1 )

(σ, r2 )

(σ, r1 )

Theorem 4.1 Let S = G × L n × Rm be a rectangular group, a = (g1 , l1 , r1 ), b = (g2 , l2 , r2 ) ∈ S. Then Cay(S, {a}) ∼ = Cay(S, {b}) if and only if or d(g1 ) = or d(g2 ). Lemma 4.2 Let S = G × L m × Rn bea rectangular group, A a nonempty subset of S, and (g1 , l1 , r1 ), (g2 , l2 , r2 ) ∈ S. Then (g1 , l1 , r1 ), (g2 , l2 , r2 ) is an arc in Cay(S, A) if and only if there exists (a, l, r2 ) ∈ A such that g2 = g1 a and l1 = l2 . As a direct consequence of Lemma 4.2, we have the following lemma. Lemma 4.3 Let S = G × L m × Rn be a rectangular group, A a nonempty subset of S. Then Cay(S, A) is the disjoint union of m isomorphic strong subgraphs (G × {li } × Rn , E i ) for i = 1, 2, . . . , m. Lemma 4.4 Let S = G × L m × Rn be a rectangular group, A a nonempty subset of S, G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, and (gk  p1 (A) × {li } × Rn , E ik ) a strong subgraph of Cay(S, A). Then the following conditions hold:

123

S. Panma, J. Meksawang w

˙ k=1 (gk  p1 (A) × {li } × Rn , E ik ); (1) (G × {li } × Rn , E i ) = ∪ (2) (gk  p1 (A) × {li } × Rn , E ik ) = Cay(gk  p1 (A) × {li } × Rn , Ai ) where Ai = {(g, li , r )|(g, l, r ) ∈ A for all l ∈ L m }. ˙w ˙w Proof (1) Note that ×  G = ∪k=1 g k  p1 (A),  then G × {li } × Rn = ∪k=1 (gk  p1 (A)  {li } × Rn ). Let (g, li , r ), (g , li , r ) ∈ E i . By Lemma 4.2, there exists (a, l, r  ) ∈ A such that g  = ga. Hence g ∈ g p  p1 (A), g  ∈ gq  p1 (A) for some p, q ∈ {1, 2, . . . , w}. A simple computation shows that p = q and then (g, li , r ), (g  , li , r  ) ∈ (g p  p1 (A) × {li } × Rn ). Because  (g p  p1 (A) × {li } × Rn , E i p ) is the strong subgraph of Cay(S, A), therefore (g, li , r ), (g  , li , r  ) ∈ w ˙w ˙w ∪˙ k=1 E ik . Hence E i ⊆ ∪ k=1 E ik . Similarly, we can prove that ∪k=1 E ik ⊆ E i , and w ˙ k=1 E ik . We conclude that (G × {li } × Rn , E i ) = ∪ ˙w then E i = ∪ k=1 (gk  p1 (A) × {li } × Rn , E ik ). i (2) Let k  p1(A) × {li } × Rn , A ), we will prove that E ik = E(D). Let  D = Cay(g (g, li , r ), (g  , li , r  ) ∈ E ik . By Lemma 4.2, there exists (a, l, r ) ∈ A such that   g  = ga. By Lemma 4.2 again,  we get that (g, li , r ), (g , li , r ) ∈ E(D). This shows that E ik ⊆ E(D). Let (g, li , r ), (g  , li , r  ) ∈ E(D). By Lemma 4.2, there exists (a, li , r  ) ∈ Ai such that g  = ga. We get that (a, j, r  ) ∈ A for some j ∈ L m . Then by Lemma 4.2 again, ((g, li , r ), (g  , li , r  )) ∈ E ik . This shows that E(D) ⊆ E ik . Therefore E ik = E(D). We conclude that (gk  p1 (A) × {li } × Rn , E ik ) = Cay(gk  p1 (A) × {li } × Rn , Ai ).   Theorem 4.5 Let S = G × L m × Rn be a rectangular group, A, B nonempty subsets of S. Let S  = G × Rn . Then Cay(S, A) ∼ = Cay(S, B) if and only if Cay(S  , A ) ∼ =    Cay(S , B ), where A = {(g, r ) | (g, l, r ) ∈ A for some l ∈ L m } and B  = {(g, r ) | (g, l, r ) ∈ B for some l ∈ L m }. Proof Let G/ p1 (A) = {g1  p1 (A), g2  p1 (A), . . . , gw  p1 (A)}, G/ p1 (B) = {h 1  p1 (B), h 2  p1 (B), . . . , h z  p1 (B)}. We let (G × {li } × Rn , E iA ), Aik = (gk  p1 (A) × {li } × Rn , E ik ) be a strong subgraph of Cay(S, A), and let (G × {l j } × Rn , E Bj ), B tj = (h t  p1 (B) × {l j } × Rn , E jt ) be a strong subgraph of Cay(S, B). By Lemma 4.3 and Lemma 4.4(1), we have Cay(S, A) ∼ = Cay(S, B) ⇔ Cay(G × L m × Rn , A) ∼ = Cay(G × L m × Rn , B) m m A ˙ i=1 (G × {li } × Rn , E i ) ∼ ⇔ ∪ = ∪˙ j=1 (G × {l j } × Rn , E Bj ) m ˙w z ˙ i=1 ˙ mj=1 ∪˙ t=1 B tj . ⇔ ∪ ∪k=1 Aik ∼ =∪

Since Aik and B tj are connected subgraphs, we get that w = z. Then for each i, k, there exist j, t such that Aik ∼ = B tj . Let DkA = (gk  p1 (A) × p2 (A ), E k ) and B  Dt = (h t  p1 (B) × p2 (B ), E t ) be strong subgraphs of Cay(gk  p1 (A) × Rn , A ) and Cay(h t  p1 (B) × Rn , B  ), respectively. Let Ai = {(g, li , r )| (g, l, r ) ∈ A}, B j = {(h, l j , r )| (h, l, r ) ∈ B}. By Lemma 4.4(2) and Theorem 3.3, we have Cay(gk  p1 (A) × {li } × Rn , Ai ) ∼ = Cay(h t  p1 (B) × {l j } × Rn , B j )

123

Isomorphism Conditions for Cayley Graphs of Rectangular…

⇔ Cay(gk  p1 (A) × Rn , A ) ∼ = Cay(h t  p1 (B) × Rn , B  ) w z ˙ k=1 DkA ∪ (gk  p1 (A) × Rn , E A ) ∼ ˙ t=1 ⇔ ∪ DtB ∪ (h t  p1 (B) × Rn , E B  ). =∪ A ∼ ˙z A ∼ B B ˙w By Lemma 3.8 and Theorem 3.5, we have ∪ k=1 Dk = ∪t=1 Dt ⇔ Dk = Dt ⇔         ∼ ∼   Cay(A , A ) = Cay(B , B ) ⇔ Cay(S , A ) = Cay(S , B ).

Example 2 Let S = S3 × L 2 × R2 be a rectangular group, where S3 = {(1), σ, σ 2 , τ, τ σ 2 , τ σ } is the symmetric group, and let A = {((1), l1 , r1 ), (τ, l1 , r1 ), (τ, l1 , r2 )}, B = {(τ σ, l2 , r1 ), ((1), l2 , r2 ), (τ σ, l2 , r2 )} be subsets of S. We have A = {((1), r1 ), (τ, r1 ), (τ, r2 )} and B  = {(τ σ, r1 ), ((1), r2 ), (τ σ, r2 )}. By Example 1, Cay(S  , A ) ∼ = Cay(S  , B  ). By Theorem 4.5, Cay(S, A) ∼ = Cay(S, B). Acknowledgments The authors would like to thank the referees for comments and suggestions on the manuscript. This work was supported by the Commission for Higher Education, the Thailand Research Fund, and Chiang Mai University.

References 1. Arworn, S., Knauer, U., Na Chiangmai, N.: Characterization of digraphs of right (left) zero unions of groups. Thai J. Math. 1, 131–140 (2003) 2. Afkhami, M., Ahmadi, M.R., Jahani-Nezhad, R., Khashyarmanesh, K.: Caley graphs of ideals in a commutative ring. Bull. Malays. Math. Sci. Soc. 37(3), 833–843 (2014) 3. Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993) 4. Chartrand, G., Lesniak, L.: Graphs and Digraphs. Chapman and Hall, London (1996) 5. Heydemann, M.-C.: Cayley graphs and interconnection networks. In: Hahn, G., Sabidussi, G. (eds.) Graph Symmetry, pp. 167–224. Kluwer, Dordrecht (1997) 6. Kelarev, A.V.: On undirected Cayley graphs. Australas. J. Comb. 25, 73–78 (2002) 7. Kelarev, A.V.: Graph Algebras and Automata. Marcel Dekker, New York (2003) 8. Kelarev, A.V.: Labelled Cayley graphs and minimal automata. Australas. J. Comb. 30, 95–101 (2004) 9. Kelarev, A.V., Praeger, C.E.: On transitive Cayley graphs of groups and semigroups. Eur. J. Comb. 24, 59–72 (2003) 10. Kelarev, A.V., Quinn, S.J.: A combinatorial property and Cayley graphs of semigroups. Semigroup Forum 66, 89–96 (2003) 11. Khosravi, B., Mahmoudi, M.: On Cayley graphs of rectangular groups. Discrete Math. 310, 804–811 (2010) 12. Kilp, M., Knauer, U., Mikhalev, A.V.: Monoids, Acts and Categories. W. de Gruyter, Berlin (2000) 13. Meksawang, J., Panma, S., Knauer, U.: Characterization of finite simple semigroup digraphs. Algebra Discrete Math. 12, 55–68 (2011) 14. Panma, S., Knauer, U., Arworn, Sr: On transitive Cayley graphs of strong semilattices of right (left) groups. Discrete Math. 309, 5393–5403 (2009) 15. Panma, S., Knauer, U., Na Chiangmai, N., Arworn, Sr: Characterization of Clifford semigroup digraphs. Discrete Math. 306, 1247–1252 (2006) 16. Panma, S.: Characterization of Cayley graphs of rectangular group. Thai J. Math. 8, 535–543 (2010) 17. Petrich, M., Reilly, N.: Completely Regular Semigroups. Wiley, New York (1999) 18. Praeger, C.E.: Finite transitive permutation groups and finite vertex-transitive graphs. In: Hahn, G., Sabidussi, G. (eds.) Graph Symmetry, pp. 277–318. Kluwer, Dordrecht (1997) 19. Sabidussi, G.: On a class of fixed-point-free graphs. Proc. Am. Math. Soc. 9, 800–804 (1958) 20. White, A.T.: Graphs, Groups and Surfaces. Elsevier, Amsterdam (2001)

123