119

数理解析研究所講究録
第2003巻 2016年 119-127

GROUPS WHOSE ALL(MINIMAL) CAYLEY GRAPHS HAVE \mathrm{A}GIVEN FORBIDDEN STRUCTURE

M. FARROKHI D. G. AND A. MOHAMMADIAN

ABSTRACT.

We give the classification of all (minimal) Cayley bipartite or per‐fect finite groups
many

as

well

as

finitegraphs $\Gamma$ for which there are only finitely(minimal) Cayley $\Gamma$ ‐free groups.

1. INTRODUCTION

Let G be a non‐trivial group and S be an inversed‐closed subset of G,

is,

S\subseteq G\backslash \{1\} and S^{-1}=\{s^{-1} : s\in S\}\subseteq S The Cayley graph of G corresponding
to S denoted by \mathrm{C}\mathrm{a}\mathrm{y}(G_{\backslash ,\prime}S) is a graph with G as the vertex set such that two\mathrm{v}\mathrm{e}\mathrm{l}\cdot tices x and y are adjacent if yx^{-1}\in S
The Cayley graph \mathrm{C}\mathrm{a}\mathrm{y}(G, S) is called
.

,

,

.

minimal if S=X\cup X^{-1} for some minimal generating subset X of G.

Cayley graphs

introduced by Arthur Cayley in 1978 as a geometric description of groups andwasplay a central role in geometric group theory. Being a source and a simple way ofconstructing symmetric graphs, Cayley graphs has became the subject of extensive
research in algebraic graph theory as well as computer science from various pointsof views.

A group in which all its associated (minimal) Cayley graphs admit a given prop‐
erty \mathcal{P} is called \mathrm{a} (minimal) Cayley \mathcal{P} ‐group. Accordingly, a Cayley integral groupis that whose all Cayley graphs are integral, that is, they all have integral spectrum.
Studying integral graphs was initiated by Harary and Schwenk [8], As an attempt

to describe integral Cayley graphs, among other works, Abdollahi and Jazaeri[1]and simultaneously Ahmady, Bell and Mohar [2] in 2014, complete the classificationof all Cayley integral finite groups.

Motivated by these works,

we

are

interested

in studying the existence of particularsubgraphs (mainly odd cycles) in Cayley
graphs associated with a finite group. More precisely, we shall give a classificationof those finite groups whose all (minimal) Cayley graphs are bipartite or perfect.
Since our main results relies on particular forbidden structures in (minimal) Cayley
graphs, we review the results on the problem that which graphs are isomorphic toan induced subgraph of \mathrm{a}(minimal) Cayley graphs and determine which graphs canbe embedded as induced subgraph into infinitely many (minimal) Cayley graphs.
The paper is organized as follows: In section 2, we show that there are only
finitely many finite Cayley $\Gamma$ ‐free groups for any finite graph $\Gamma$ while the same
result for minimal Cayley $\Gamma$ ‐free groups holds if and only if $\Gamma$ is a union of somepaths. We note that a $\Gamma$ ‐free graph is one having no induced subgraph isomorphic
to $\Gamma$ Section 3 gives a description of all (minimal) Cayley bipartite groups, that is,finite groups whose all (minimal) Cayley graphs have no odd cycles as subgraphs.
.

2010 Mathematics Subject

Classification. Primary 05\mathrm{C}25 ; Secondary 20\mathrm{F}05, 05\mathrm{C}17, 05\mathrm{C}3\mathrm{S}.
Key words and phrases. Cayley graph, perfect graph, bipartite graph, forbidden subgraph.

120
FARROKHI AND MOHAMMADIAN

Finally, in section 3, we shall restrict our attention to induced odd cycles anddetermine all (minimal) Cayley perfect finite groups by using the knowledge of
their forbidden induced odd cycles. Recall that a graph is perfect if the chromaticand clique number of its induced subgraphs coincides. A celebrated theorem ofChudnovsky, Robertson, Seymour and Thomas [5], known as the strong perfectgraph theorem, states that a graph $\Gamma$ is perfect if and only if neither $\Gamma$ nor its
complement has induced odd cycles other that triangles.
Throughout this paper, we adopt the following notations: Given a group G,
the minimum size of generating set of G is denoted by d(G) An arbitrary Sylow
p‐subgroup of G will be denoted by S_{p}(G)Also, E_{p} stands for the extra‐special
p‐group of order p^{3} and exponent p The unexplained notions are standard and canbe found in any standard book. Recall that the Frattini subgroup $\Phi$(G) of G is theintersection of all maximal subgroups of G It is known that $\Phi$(G) is the set of all
.

.

.

.

non‐generators of G , the fact that will be used without further references.
2.

(MINIMAL) CAYLEY $\Gamma$ ‐FREE GROUPS

Every graph can be simply embedded as induced subgraph into some Cayley
graph of sufficiently large order, namely using an elementary abelian 2‐group gen‐erated freely by the vertices of the graph. As an attempt to decrease the exponential
order of the corresponding Cayley graphs, Babai and Sos in [4], using the analysis

9.5| $\Gamma$|^{3} for the order of a group G whichof Sidon sets, gave a cubic lower bound,the existence of a Cayley graph on G having $\Gamma$

assuresasaninduced subgraph.

This lower bound is further improved to (2+\sqrt{3})| $\Gamma$|^{3} by Godsil and Imrich in [7].
Hence, we have the following.
Theorem 2.1.

For every finite

bounded above by(2+\sqrt{3})| $\Gamma$|^{3}.

graph $\Gamma$,

the orderof a Cayley $\Gamma$ ‐free group is

While every graph is an induced subgraph of a Cayley graph, it is still unknown
which graphs can be embedded as (induced) subgraph into some minimal Cayley
The only known results are due to Babai and Spencer.

graphs.

Indeed, Babai [3]as subgraph,shows that there is no minimal Cayley graphs having K_{4}\backslash e or K_{3,5}in which

K_{4}\backslash e is the diamond graph. Spencer [11], using the ideas of Babaiand utilizing probabilistic arguments, proves the existence of graphs of bounded
degree and arbitrary girth which cannot be embedded into minimal Cayley graphs

as induced subgraphs. In contrast to the above theorem, the situation for minimal
Cayley $\Gamma$ ‐free groups is completely different as follows.

Theorem 2.2. Let $\Gamma$ be a finite graph. Then there are only finitely many minimal

Cayley $\Gamma$ ‐free groups if and only if $\Gamma$ is a union of paths. Moreoveri |G|<| $\Gamma$|^{| $\Gamma$|} forany minimal Cayley $\Gamma$ ‐free group G when $\Gamma$ is a union of paths.

Proof. Suppose $\Gamma$ is a graph for which there are just finitely many minimal Cayley
Since all minimal Cayley graphs of C_{2^{n}} are isomorphic to the 2^{n_{-}}
itfollows that $\Gamma$ is an induced subgraph of 2^{n} ‐cycles for sufficiently
cyclic graph,nHence, $\Gamma$ is a union of paths. Conversely, suppose $\Gamma$ is a union of paths.
large
Let G be a minimal Cayley $\Gamma$ ‐free group and $\Gamma$`=\mathrm{C}\mathrm{a}\mathrm{y}(G, S) be a minimal Cayley
graph of G in which S=X\cup X^{-1} and X=\{x_{1}, . . . , x_{n}\} is a minimal generating
set of G Also, let N_{i} denote the ith neighbor of the identity element in $\Gamma$ , that is,
N_{i}=\{g\in G : d_{$\Gamma$'}(1, g)=i\} for all i\geq 0 Clearly, |N_{0}|=1 and |N_{i}|\leq r(r-1)^{i-1}$\Gamma$ ‐free groups.

.

.

.

121
(MINIMAL) CAYLEY \mathcal{P} ‐GROUPS

for all i\geq 1 in which r=|S| is the degree of $\Gamma$ . If d=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}($\Gamma$') , then N_{d}\neq\emptyset andN_{d+1}=\emptyset which imply that,

|G|=|N_{0}|+|N_{1}|+\cdots+|N_{d}|\displaystyle \leq 1+r+r(r-1)+\cdots+r(r-1)^{d-1}=1+r\cdot\frac{(r-1)^{d}-1}{r-2}.
Since, every path connecting 1 to any element of N_{d} is an induced path of length d
in $\Gamma$ , it follows that d<| $\Gamma$|-1 On the other hand,.

x_{1}\sim x_{2}x_{1}\sim\cdots\sim x_{n}\cdots x_{1}\sim x_{1}x_{n}\cdots x_{1}\sim\cdots\sim x_{n-1}\cdots x_{1}x_{n}\cdots x_{1}

is an induced path in $\Gamma$' , which implies that 2n-1\leq dthat |G| is bounded above by
3.

| $\Gamma$|^{| $\Gamma$|}

,

as

.

Since r\leq 2n , we observe\squarerequired.

( MINIMAL ) CAYLEY BIPARTITE GROUPS

It is well‐known that bipartite graphs

areperfect. Hence, in order to classify(minimal) Cayley perfect groups, we need to know the structure of (minimal) Cayley
bipartite groups. As we shall see in the next section, almost all (minimal) Cayley
perfect groups are (minimal) Cayley bipartite groups.
Since the only bipartite complete graphs are those with at most 2 vertices, theonly Cayley bipartite groups are simply groups with at most 2 elements. Hence,in what follows, we just consider minimal Cayley bipartite groups. To end this, we
use the following characterization of finite bipartite
Cayley \mathrm{g}_{1}\cdot aphs.
Lemma 3.1. Let G be a finite group. A

only if [G:\langle S^{2}\rangle]=2 and S\subseteq G\backslash \{S^{2}\}.

Cayley graph \mathrm{C}\mathrm{a}\mathrm{y}(G, S) is bipartite if andProof. Suppose \mathrm{C}\mathrm{a}\mathrm{y}(G, S) is bipartite with a bipartition (X, Y) Let H=\{S^{2}\rangle.
Since, sX\subseteq Y and sY\subseteq X for all s\in S it follows that |X|=|Y|=|G|/2 In
addition, s_{1}s_{2}X=X and s_{1}s_{2}Y=Y for all s_{1}, s_{2}\in S which imply that HX=X
and HY=Y
Since H contains all products of even number of elements of S,
.

.

,

,

.

must have s_{1}H=s_{2}H for all s_{1}, s_{2}\in S whence [G:H]=2 and S\subseteq G\backslash H.
\squareMoreover, X and Y are right cosets of H The converse is obvious.

we.

Theorem 3.2. A finite group G is a minimal Cayley bipartite group if and only if
it is a 2‐group.

Proof. First assume that G is a minimal Cayley bipartite group.
intersection of all subgroups of G of index 2.

graph of G,

If \mathrm{C}\mathrm{a}\mathrm{y}(G, S) isa

Let K be theminimal Cayley

then S\subseteq G\backslash H for some subgroup H of G of index 2 by Lemma 3.1.

K\cap S=\emptyset from which it follows that K\subseteq $\Phi$(G) theThus, G/ $\Phi$(G) is a 2‐group so that G is a 2‐group too.
Conversely, assume G is a 2‐group. If \mathrm{C}\mathrm{a}\mathrm{y}(G, S) is a minimal Cayley graph of G,
then S=X\cup X^{-1} where X=\{x_{1}, . . . jx_{n}\} is a minimal generating set of G Let
Since K\subseteq H ,

have

we

Frattini subgroup of G

,

,

.

,

.

H=\{ $\Phi$(G), x_{1}x_{2}, . . . , x_{1}x_{n}\}.

Then H is a maximal subgroup of G and S\subseteq G\backslash H.

Hence, by Lemma 3.1, \mathrm{C}\mathrm{a}\mathrm{y}(G, S) is bipartite. Therefore, G is a minimal Cayley\squarebipartite group.
4.

(MINIMAL) CAYLEY PERFECT GROUPSIn this section, we shall give a classification of those finite groups all of whose
minimal Cayley graphs are perfect.

As a result we show that there are only few

Cayley perfect groups. The following simple lemma will be used frequently.

122
FARROKHI AND MOHAMMADIAN

Lemma 4.1. Let G=\langle g) be a cyclic group.

Then(1) \mathrm{C}\mathrm{a}\mathrm{y}(G, \{g^{\pm 2_{j} g^{\pm 3}\}) has an induced 5‐cycle 1\sim g^{2}\sim g^{4}\sim g^{6}\sim g^{3}\sim 1 for|g|\geq 10 ; and(2) \mathrm{C}\mathrm{a}\mathrm{y}(G, \{g^{\pm 1}, g^{\pm 4}\}) has an induced 5‐cycle 1\sim g\sim g^{2}\sim g^{3}\sim g^{4}\sim 1 for|g|\geq 8.
The proof of our theorems rely also on the following result of the first author.
In what follows, -:G\rightarrow G/ $\Phi$(G) denotes the natural epimorphism, in which G isagiven fixed \mathrm{g}_{1}\cdot \mathrm{o}\mathrm{u}\mathrm{p}.

([6]). Let G be a finite solvable group and P be a Sylow p ‐subgroupof G. If either \overline{P}\underline{\triangleleft}G or \overline{P} is cyclic, then d(P)=d(\overline{P})Theorem 4.2.

Now, we can state and prove our main results.
Theorem 4.3. A finite group G is a minimal Cayley perfect group if and only ifeither G is a 2‐group.

or

it is isomorphic to one of the groups C_{3}, C_{6_{i}}S_{3},C_{3}\times C_{3_{4}}A_{4} or E_{3}.

Proof. From Theorem 3.2, we know that every 2‐group is a minimal Cayley perfectgroup. Also, a simple verification shows that the other six groups are also minimal
Cayley perfect groups.
To prove the converse assume that G is a minimal Cayley perfect group andthat G is not a 2‐group. Hence G\backslash $\Phi$(G) contains an element g of odd order.
Let X be a minimal generating set of G containing g and S=X\cup X^{-1}Then
the subgraph induced by \{g\} in \mathrm{C}\mathrm{a}\mathrm{y}(G, S) is an odd cycle, which implies that|g|=3 Hence, G is a {2, 3}‐group. Let Q be a Sylow 3‐subgroup of G If\exp(Q)\neq 3 then S_{3}( $\Phi$(G))=H_{3}(Q) is a maximal \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{g}_{1}\cdot\mathrm{o}\mathrm{u}\mathrm{p} of Q by [12], inwhich H3 (Q)=\{x\in Q : x^{3}\neq 1\rangle From the solvability of G in conjunction with
Theorem 4.2, we observe that Q is cyclic and hence Q\cong C_{3} a contradiction. Thus\exp(Q)=3 First assume that G=Q is a 3‐group. If d(G)\geq 3 and a, b, c areelements of a minimal generating set X of G then we observe that
.

.

,

.

,

.

,

1\sim c\sim bc\sim abc\sim cabc\sim bcabc\sim abcabc\sim

cabcabc\sim

bcabcabc\simlis an induced 9‐cycle in \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1}) arose from the relation (abc)3 =1 , which

is a contradiction. Thus d(G)\leq 2
2 so that|G|\leq 27

Finally,.

By [10, 12.3.5], G is a group of nilpotent class

As a group of exponent 3, G\cong C_{3} C3 \times C_{3} or E_{3}.
assume that G is neither a 2‐group nor a 3‐group.
Let C be the class.

,of all groups isomorphic to C_{6} ,S3 or A_{4} A simple computation shows that, in a
12, a minimal generating set involving an element of order 3gives rise to a perfect Cayley graph only if the group belongs to C We show that
G\in C too. Assume G is a minimal counter example. Let l_{f} be the number of
non‐Frattini factors in a chief series of G First assume that l_{f}=2 One can easily
see that \overline{G}\cong C_{6}S3 or A_{4} We have three cases:
Case 1. \overline{G}\cong C_{6} Then G is cyclic. If |G|>6 then G has a minimal Cayley
graph with an induced 5‐cycle as illustrated in Lemma 4.1(1), a contradiction. Thus
G\cong C_{6} a contradiction.
Case 2. \mathrm{G}\cong S_{3} From [6] we know that G=\langle x, y : x^{3}=y^{2^{k}}=1, x^{y}=x^{-1} }.

group of order 6 or

.

.

.

.

,

.

,

,

.

for some k\geq 1.

For k\geq 2 , the relation

cycle of length 2^{k}+3 in \mathrm{C}\mathrm{a}\mathrm{y}(G,G\cong S_{3},acontradiction.

y^{2^{k}-2}xyx^{-1}yx=1 defines\{x^{\pm 1}, y^{\pm 1}

Hence,

wean

induced odd

must have k=1

so

that

123
(MINIMAL) CAYLEY \mathcal{P} ‐GROUPS\overline{G}\cong A_{4}Case 3.

.

Then \overline{G}=\langle\overline{x}, \overline{y}:\overline{x}^{2}=\overline{y}^{3}=(\overline{xy})^{3}=\overline{1} }.

Let P and Q be

the Sylow 2‐subgroup and a Sylow 3‐subgroup of G , respectively.

By Theorem 4.2,

P=\{x, x^{y}) is a maximal subgroup of G and Q\cong C_{3} We may assume Q=\{y\rangle.
If Q^{x}\subseteq $\Phi$(P)Q then x^{-y}x=[y, x]\in $\Phi$(P) which is impossible as x^{-y}x is a
generator of P Thus y^{X}=x'y for some x\in P\backslash $\Phi$(P) Hence, replacing x by x' ifnecessary, we may assume that (xy)3 =1 from which it follows that x^{y^{-1}}x^{y}x=1.
Clearly, |x|=2^{m}>2 for G\not\cong A_{4} Since the group \langle a, b : a^{2^{r $\iota$}\prime}=b^{2^{7r $\iota$}}=(ab)^{2^{r $\iota$}\prime}=1 }
.

,

,

.

.

,

.

is infinite, there must exists a relation w=1 in x, x^{y} independent of the relationsx^{2^{\prime r $\iota$}}=1, (x^{y})^{2^{\prime n}}=and (x^{y}x)^{2^{rr $\iota$}}=1
Assume w has minimum length among
Clearly, |w|\geq 7 in which |w| denotes the length of |w| as aword in x, y After a suitable cyclic shift and inverse if required, we may assume
that w=x^{a_{1}y}x^{b_{1}}\cdots x^{a_{k}y}x^{b_{k}} in which a_{i}, b_{i}\neq 0 for i=1
k, a_{1}>0 andLet
us call a word in x, x^{y} is good if it has even(a_{1}, b_{1})\neq(1,1)
length as a word
in x_{\dot{1}}x^{y} Since \mathrm{C}\mathrm{a}\mathrm{y}(P, \{x^{\pm 1_{i} x^{\pm y}\}) is bipartite by Theorem 3.2 and y\not\in P one caneasily see that a subword u of a good word u^{*} equals an element g\in\{1, x^{\pm 1}, y^{\pm 1}\}
only if either g^{-1}u or ug^{-1} is a good subword of u^{*} Having this in mind, w=1
gives rise to an induced odd cycle in \mathrm{C}\mathrm{a}\mathrm{y}(G, \{x^{\pm 1}, y^{\pm 1}\}) when |w| is odd, which is.

all such relations.
.

,

.

.

.

,

.

.

,

.

a

contradiction.

Thus|w| is even.

From w=1 we may construct a new relation

w'=1 , where w' is defined asw'=x^{-y^{-1}}x^{-1}x^{(a_{1}-1)y}x^{b_{1}}x^{a_{2}y}x^{b_{2}}\cdots x^{a_{k}y_{X}b_{k}}.
Suppose w' has a proper subword w'' which is equal to an element g\in\{1, x^{\pm 1}, y^{\pm 1}\}and that neither g^{-1}w'' nor wg‐l is a subword of w' otherwise we may replacew'' by g^{-1}w^{Jl} or w^{;}g^{-1} and g by 1. If w'' is a subword of x^{y^{-1}}w' then, by theargument above, either g^{-1}w' or wg‐l is a good subword of x^{y^{-1}}w' and we may
assume w=1
Moreover, w'=x^{-1}x^{-y}w should be an initial subword of x^{y^{-1}}w'.

in which w^{;/} isa good initial subword of w
But then, it follows that w=x^{y}x
contradicting the assumption on a_{1}, b_{1} and the length of w Hence w'' should.

.

contain some letters of the initial term x^{-y^{-1}} of w'

of w , then sinceg^{-1}w''\equiv wg‐1 \equiv 1(\mathrm{m}\mathrm{o}\mathrm{d} P)

,

.

If w

we



is not an initial subword

must havearelation of theform yw'' y=1 in which either ywly is an initial subword of x^{y^{-1}}w'atx^{$\alpha$_{i}'y} with |a_{i}|<|a_{i}| as a subword of x^{a_{i}y}=x^{a_{i}'y}x^{(a_{i}-a_{i}')y}.

orw' ends

Since the former

ruled out by the above discussions, (ywy)^{-1}w'=1 is a relation in whichcase was(yw''y)^{-1}w is a proper subword of w contradicting the assumption on w Thus
w''=x^{-y^{-1}}x^{-1}w^{J} is an initial subword of w' possessing the initial term x^{-y^{-1}}x^{-1}.
.

But then x^{y}w=g where x^{y}w^{;}g^{-1}org^{-1}x^{y}w

is a proper subword of w after

possibly a cyclic shift contradicting the assumption on w Now, the relation w'=1
determines an induced odd cycle of length |w'|=|w|+1 in \mathrm{C}\mathrm{a}\mathrm{y}(G, \{x^{\pm 1}, y^{\pm 1}
the.

final contradiction.

In the sequel, we assume that l_{f}\geq 3.

Let$\Phi$(G)=G_{0}\underline{\triangleleft}G_{1}\underline{\triangleleft}\ldots\underline{\triangleleft}G_{l-1}\underline{\triangleleft}G_{l}=G,
be the inverse image of a chief series of G/ $\Phi$(G) andassumeM=G_{l-1}.

From[9, Theorem 2], we know that G has a minimal generating set X=\{x_{1}, . . . , x_{l_{f}}\}x_{i}\in G_{n_{i}}\backslash G_{n_{i}-1}(i=1, \ldots, l_{f}) is an element of prime power order,n_{1}=1, n_{f}=l and G_{n_{i}}/G_{n_{i}-1} are the non‐Frattini factors of the chief series, fori=1l_{f} Replacing the elements of X by suitable conjugates, we can also
assume that x_{i},x_{j} belong to the same Sylow p ‐subgroup whenever x_{i}, x are bothin which

,

.

.

.

,

.

124
FARROKHI AND MOHAMMADIAN

p‐elements for some p=2 , 3. Let Y_{i}=X\backslash \{x_{i}\} for i=1 ,every x_{i} belongs to some Y_{j}

.

.

.

l_{f}

,

.

First observe thehaving elements of odd and even orders.

Hence, byassumption on G and perfectness of \mathrm{C}\mathrm{a}\mathrm{y}(\langle Y_{j}\rangle, Y_{j}\cup Y_{j}^{-1}) it follows that \langle Y_{i} } \in C
so that x_{i} has prime order. Furthermore,l_{f}=3.
We claim that l=l_{f} that is, there are no Frattini factors. Clearly, Y_{i} contains
elements of order 2 and 3 for some i\in\{1 2 \} Then G=G_{n_{2}}\langle Y_{i}\rangle implies G/G_{n_{2}}\cong\{Y_{i}\}/(G_{n_{2}}\cap\{Y_{i}))\cong C_{2} or C_{3} Hence, n_{2}=n_{3}-1=l-1 Therefore, $\Phi$(G/G_{1})=G_{l-2}/G_{1} On the other hand, we have G/G_{1}=\{G_{1}x_{2}, G_{1}x_{3}\} In case \{|x_{2}|, |x_{3}|\}=\{2 3 \} we have \{x_{2}, x3\}\in C showing that l=3 If |x_{2}|=|x_{3}|=2 then G/G_{1}is a dihedral 2‐group.
Clearly, \{x_{1}, x_{2}x_{3}, x3\} is a minimal generating set of G
forcing (x_{2}x_{3})^{2}=1 Hence, G_{l-2}=\{G_{1}, (x_{2}x_{3})^{2}\}=G_{1} and again l=3 Finally,
assume that|x_{2}|=|x_{3}|=3 Being a 2‐generated 3‐group of exponent 3, G/G_{1}
is isomorphic to C3 \times C_{3} or E_{3} Assume G/G_{1} is non‐aUelian. If x_{2} X3 commute
with x_{1} then G=\langle x_{1} } \times\langle x_{2} x3} so that [x_{2}, x3]\in $\Phi$(G) a contradiction. Hence,
,

,

.

,

.

.

.

.

,

,

.

,

.

.

.

.

,

we

may

,

,

assume[x_{1}, x3]\neq 1

that

,

.

If [x_{1}, x_{2}x_{3}]\neq 1 , then since\{x_{1}, x_{2}x_{3\backslash \prime} X3\} is aminimal generating subset of G, \{x_{1}, x_{2}x_{3}\}\cong A_{4} by assumption on G

Accordingly,.

(x_{1}x_{2}x_{3})^{3}=1 giving rise to an induced 9‐cycle in \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1}) , a contradiction.

Thus, by replacing x_{2} by x_{2}x_{3} if required, we may assume that x_{1} and x_{2} commute.
[x_{1}, x_{2}x_{3}^{-1}]\neq 1 and \{x_{1}, x_{2}, x_{2}x_{3}^{-1}\} is a minimal generating subset of G we

Since

,

observe thatx_{1}x_{1}^{x_{3}^{-1}x_{2}^{-1} =(x_{1}x_{1}^{x_{3}^{-1} )^{x_{2}^{-1} =x_{1}^{x_{3}x_{2}^{-1} =x_{1}^{(x_{2}x_{3}^{-1})^{-1} =x_{1}x_{1}^{x_{2}x_{3}^{-1} =x_{1}x_{1}^{x_{2}^{-1}x_{3}^{-1}which

implies that [x_{2}, x3] commutes with x_{1}and one can verify that.

Hence, G=\langle x_{1}, x_{1}^{x_{3} } $\lambda$\{x_{2}, x3\}

[x_{2}, x3]\in $\Phi$(G) , which is a contradiction.

Thus G/G_{1} isabelian and consequently l=3 , as required. In addition, we have shown that when|x_{2}|=|x_{3}|=p either \langle x_{2}, x_{3} } \cong C_{p}\times C_{p} or G\cong E_{3} with [x_{2}, x3]\in $\Phi$(G),Further we show that every involution x_{u}\in X acts by inversion on

that$\Phi$(G) is elementary abelian when \{x_{u}, x_{v}\}\cong A_{4} for some x_{v}\in X

let g\in $\Phi$(G)$\Phi$(G) and

To end this,Since x_{u} can be replaced with gx_{u} in X , we deduce that (gxu)2 =1,.

that is, g^{x_{u}}=g^{-1}.

Replacing x_{u} by x_{u}^{x_{v}^{\pm 1} in X results in a new minimal generating

subset, from which it follows that
as

.

.

claimed.

g^{x_{u}^{x_{v} }\pm 1=g^{-1} Hence, g^{-1}=g^{x_{u^{-1} ^{x_{v} }=g^{x_{\mathrm{Y}1}x_{\mathrm{u} ^{x_{V} }=g,.

Now, put H=\langle Y_{3}\rangle Since \mathrm{C}\mathrm{a}\mathrm{y}(H, Y_{3}\cup Y_{3}^{-1}) is an induced subgraph of \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup
X^{-1}) it is perfect. We distinguish three cases:
Case 1. H is a 2‐group. Then [G:M]=3 and M is the Sylow 2‐subgroupof G by Theorem 4.2 and the fact that the Sylow 3‐subgroups of G have exponent
three. Moreover, since $\Phi$(G)= $\Phi$(M) it follows that \overline{M} is elementary abelian.
As \mathrm{C}\mathrm{a}\mathrm{y}(\{Y_{i}\}, Y_{i}\cup Y_{i}^{-1}) is perfect for i=1 2, the minimality of G shows that\{Y_{i}\}\in C and subsequently \{Y_{i}\}\cong C_{6} or A_{4} Hence, |\overline{M}|\leq 16 First suppose that\langle x_{1} x3 \}\cong\langle x_{2} x3 \}\cong C_{6} Then M=H, G/ $\Phi$(G)\cong C_{6}\times C_{2} and G is nilpotent. If
.

,

,

,

.

,

,

.

.

M\backslash $\Phi$(M) contains an element x of order \geq 4 then Lemma 4.1(1) shows that the,

Cayley graph corresponding to every minimal generating subset of G containing x
and x3 contains an induced 5‐cycle, a contradiction. Thus M\backslash $\Phi$(M) contains only
involutions, which yields M\cong C_{2}\times C_{2} Hence, G\cong C_{6}\mathrm{x}C_{2} contradicting the
choice of G Thus, \langle x_{i}, x3 ) \cong A_{4} for some i=1 2. We show that \langle x_{j}, x_{3}\rangle\cong C_{6} forj\in\{1, 2\}\backslash \{i\} Indeed, if \{x_{2}, x_{3}\rangle\cong A_{4} then \{x_{1}, x_{2}, x_{2}x_{3}\} is a minimal generating
.

.

,

.

,

subset of G and |x_{2}x_{3}|=3 , from which it follows that \{x_{1}, x_{2}x_{3}\}\cong C_{6}.

Otherwise(x_{1}x_{2}x_{3})^{3}=1 and hence we obtain an induced 9‐cycle in \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1})

.

Thus,

125
(MINIMAL) CAYLEY \mathcal{P} ‐GROUPS

by replacing X3 by x_{2}x_{3} if necessary, we may assume that x_{1} and X3 commute, as
required. Hence, $\Phi$(G) is elementary abelian as shown before. For g\in $\Phi$(G) we,-1(gx_{i})^{x_{3}}=(gx_{i})(gx_{i})^{x_{3}} and (gx_{j})^{x_{3}}= (gxj) for x_{i} can be replaced
in
X
Thus
by gx_{i}g^{x_{3}^{-1}}=gg^{x_{3}}=1 which yields g=1 Therefore, $\Phi$(G)=1.
itis
obviousthat
G\cong A_{4}\times C_{2}Now,
Putting a:=x_{3}^{x_{i}} and b:=x_{j}x_{3)} weobserve that G=\langle a, b\rangle and \mathrm{C}\mathrm{a}\mathrm{y}(G, \{a^{\pm 1}, b^{\pm 1}\}) has an induced 7‐cycle determined
observe that

.

.

,

.

by b^{-1}abab^{2}a^{-1}=1 which is impossible.
Case 2. H is a 3‐group. Then [G : M]=2 and M is the Sylow 3‐subgroup of G
by Theorem 4.2. As in case 1 for i=1 2, we have \langle Y_{i}\rangle\in C showing that \{Y_{i}\rangle\cong C_{6}or S_{3}Hence, x_{i}^{x_{3} =x_{i}^{$\epsilon$_{i} with $\epsilon$_{i}=\pm 1 for i=1 2. Moreover, M=H is a group
,

,

,

.

,

of order 9 or 27.

Let

w=x_{2}x_{1}^{-1}x_{2}^{-1}x_{1}Then \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1}) has an induced.

7‐cycle or 11‐cycle determined by the relation x_{3}x_{2}^{$\epsilon$_{2}}x_{1}^{-$\epsilon$_{1}}x_{3}x_{2}x_{1}wx_{2}=1 according
w=1 or not, respectively, which is a contradiction.
Case 3. H is neither a 2‐group nor a 3‐group. By assumption, H\in C so that
Let k\in\{1 2 \}H\cong C_{6} S3 or A_{4} Assume |x_{i}|=2 and |x_{j}|=3 for \{i, j\}=\{1 2
be such that |x_{k}|\neq|x_{3}| As { x_{k}, x_{3}\rangle\in C we also have \langle x_{k}, x_{3} } \cong C_{6} S3 or A_{4}.
First assume that |x_{2}|=|x_{3}|=p If p=2 then [x_{2}, x3]=1 and x_{1}^{x_{2} , x_{1}^{x_{3}}\in\{x_{1}\rangle,
from which it follows that G\cong C_{6}\times C_{2} or S3 \times C_{2} contradicting the assumption
on G
Thus p=3 As in case 1, we may assume that x_{1} commutes with X3 andconsequently x_{1} commutes with [x_{2}, x3] as shown before. Hence, G=\{x_{1}\}\times\{x_{2} x3)
as

.

,

,

.

,

,

,

.

.

.

,

if [x_{1}, x_{2}]=1 and

G=\{x_{1}, x_{1}^{x_{2} \rangle\rangle\triangleleft\{x_{2}, X3\} if [x_{1}, x_{2}]\neq 1x_{1}x_{2}x_{3}x_{2}^{-1}x_{1}x_{2}^{-1}x_{3}x_{2}x_{3}=1 determines
contradiction.
w=1

orinduced 9‐cycle in \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1}) , \mathrm{a}an(x_{1}x_{2}x_{3})^{2}wx_{1}x_{3}x_{2}=1 in which

Also, in the latter case, the relationx_{2}^{-1}x_{3}^{-1}x_{2}x_{3} accordingas

In the former case,.

[x_{2}, x3]=1 or not, determinesaninduced\mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1}) , respectively, which is a contradiction.

9‐cycleIf x_{2} and X3 commute, thenThus, we have left with the case |x_{2}|\neq|x_{3}|we can interchanging x_{2} and x3 after which H will be a
2‐group or a 3‐group.
without
lossof
we
assumethatHence,
generality,[x_{2}, x3]\neq 1 In the case x_{1}or

13‐cycle in.

.

\{x_{2}, x_{2}^{x_{3} , x_{2}^{x_{3}^{-1} \} isand x_{2} commute,anelementary abelian normal subgroup of G

otherwise [x_{1}, x3] does not commutes with x_{2} so that(x_{1}^{x_{3}})^{-1}.

[x_{1}, x_{3}]^{x_{2}}=x_{1}[x_{3}, x_{1}]Thenminimal generating subset of G

.

,

which

\{x_{2}, x3 ) \cong A_{4} and (x_{1}^{x_{3}})^{x_{2}}=implies that \{[x_{1}, x_{3}], x_{2}, x3\} is a

But then, we must have \{[x_{1}, x_{3}], x_{2} ) \cong C_{6} or S_{3},which is impossible. It means we can also interchange x_{1} and x_{2} after which we arein the situation that|x_{2}|=|x_{3}| as discussed above. Thus, we may further assume\{x_{1}, x_{2}\rangle and \{x_{k}, x3\} are isomorphic to S3 and A_{4} insome order, which implies that$\Phi$(G) is an elementary abelian subgroup of G Now,
we have only two possibilities.
If (|x_{1}|, |x_{2}|, |x_{3}|)=(2,3,2) then \langle x_{1}, x_{2}\rangle\cong A_{4}and \langle x_{2} x3 \}\cong S_{3} Clearly, \{x_{1} x3) is a dihedral 2‐group. If |x_{1}x_{3}|=2^{m} then wethat [x_{1}, x_{2}]\neq 1.

As a result,

.

,

,

.

,

,

observe that \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1}) containsby (x_{1}x_{2})^{2}(x_{3}x_{1})^{2^{m}-1}x_{2}x_{3}x_{2}^{-1}=1(|x_{1}|, |x_{2}|, |x_{3}|)=(3,2,3)

Let

.

,

an

induced(2^{m+1}+5) ‐cycle determinedwhich is a contradiction.

Thus, we should have

Then \{x_{1}, x_{2} ) \cong S_{3} and \langle x_{2}, x_{3}\rangle\cong A_{4} , hence |x_{2}x_{3}|=3.

Q be a Sylow 3‐subgroup of G containing x_{2}x_{3} Let y\in $\Phi$(G)\{x_{2}, x_{2}^{x_{3} \rangle, \mathrm{a}Sylow 2‐subgroup of G be such that x_{1}^{y}\in Q Replacing x_{1} by x_{1}^{y} in X one canassume that x_{1}\in Q
Being elements of Q it follows that (x_{1}x_{2}x_{3})^{3}=1 giving riseto an induced 9‐cycle in \mathrm{C}\mathrm{a}\mathrm{y}(G, X\cup X^{-1}) the final contradiction. The proof is\squarecomplete.
.

,

.

.

,

,

,

126
FARROKHI AND MOHAMMADIAN

Utilizing the above theorem, it is now easy to obtain the classification of all
Cayley perfect finite groups.
Theorem 4.4. Let G be a nontrivial finite group. Then G is a Cayley perfect group

if and only if G is isomorphic to one of the groups C_{2}. C_{3}, C_{4}. C_{2}\times C_{2}. S_{3}. C_{6}.
C_{2}\times C_{2}\times C_{2}. C_{2}\times C_{4}. D_{8}. Q_{8:} C3 \times C_{3}.

Proof. Assume G is a Cayley perfect group. By Theorem 4.3, either G is a 2‐group
G is isomorphic to one of the \mathrm{g}\mathrm{l}\cdot oups C C_{6}, S_{3} C3 \mathrm{x}C_{3}, A_{4} or E_{3} From rows(g) and (10) of Table I, it follows that G\not\cong A_{4} and E_{3} Furthermore, if G is a
2 group, by Lemma 4.1(2) and rows (1) -(8) of Table I, we observe that |G|\leq 8.
Hence, G\cong C_{2}, C_{4}, C_{2}\times C_{2}, C_{4}\times C_{2}, C_{2}\times C_{2}\times C_{2}, D_{8} or Q_{8} and the result
follows. The converse is straightforward.
\square
or

,

,

.

.

REFERENCES[1] A. Abdollahi and M. Jazaeri, Groups all of whose undirected Cayley graphs are integral,
European J. Combin. 38 (2014), 102‐109.
[2] A. Ahmady, J. Bell and B. Mohar, Integral Cayley graphs and groups, SIAM J. Discrete Math,28(2) (2014), 685−701.
[3] L. Babai, Chromatic number and subgraphs of Cayley graphs, Theory and applications ofgraphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), pp. 1 + 22.
[4] L. Babai and V. T. Sós, Sidon sets in groups and induced subgraphs of Cayley graphs, European
J. Combin. 6 (1985), 101‐114.
[5] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem,
Ann. of Math. (2) 164(1) (2006), 51‐229.
[6] M. Farrokhi D. G., Finite groups with a given Frattini factor group, In preparation.
[7] C. D. Godsil and W. Imrich, Embedding graphs in Cayley graphs, Graphs Combin. 3 (1987),
39‐43.

[8] F. Harary, A. J. Schwenk, Which graphs have integral spectra? Lecture Notes in Mathematics
406, Springer, 1974, pp. 45‐51.

[9] A. Lucchini, The largest size of a minimal generating set of a finite group, Arch. Math. (Basel)
101 (2013), 1‐8.
[10] D. J. S. Robinson, A Course in the Theory of Groups, Second Edition, Springer‐Verlag, New
York, 1996.

[11] J. Spencer, Whats not inside a Cayley graph, Combinatorica 3(2) (1983), 239‐241.
[12] E. G. Straus and G. Szekeres, On a Problem of D. R. Hughes, Proc. Ame $\tau$ Math. Soc. 9(1)(1958), 157−158.
.

127(MINIMAL) CAYLEY \mathcal{P} ‐GROUPSMATHEMATICAL SCIENCE RESEARCHOF

UNIT, COLLEGE OF LIBERAL ARTS: MURORAN INSTITUTETECHNOLOGY, 27‐1. MIZUMOTO, MURORAN 050‐8585. HOKKAIDO, JAPAN.

E‐mail address:

m.farrokhi.d.g@gmail.com

DEPARTMENT OF PURE MATHEMATICS, FERDOWSI UNIVERSITY OF MASHHAD, MASHHAD, IRAN.
E‐mail address:

abbasmohmmadian8421@gmai1.com