# The Cyclic Graph of a Finite Group

Authors: Xuan Long Ma; Hua Quan Wei; Guo Zhong
Journal: Algebra
 (2013)

---

## Abstract

The cyclic graphΓG of a finite group G is as follows: take G as the vertices of ΓG and join two distinct vertices x and y if 〈x,y〉 is cyclic. In this paper, we investigate how the graph theoretical properties of ΓG affect the group theoretical properties of G. First, we consider some properties of ΓG
and characterize certain finite groups whose cyclic graphs have some properties. Then, we present some properties of the cyclic graphs of the dihedral groups D2n and the generalized quaternion groups Q4n for some n.
Finally, we present some parameters about the cyclic graphs of finite noncyclic groups of order up to 14.


---

## Body

## 1. Introduction and Results

Recently, study of algebraic structures by graphs associated with them gives rise to many interesting results. There are many papers on assigning a graph to a group and algebraic properties of group by using the associated graph; for instance, see [1–4].LetG be a group with identity element e. One can associate a graph to G in many different ways. Abdollahi and Hassanabadi introduced a graph (called the noncyclic graph of a group; see [4]) associated with a group by the cyclicity of subgroups. It is a graph whose vertex set is the set G∖Cyc(G), where Cyc(G)={x∈G|〈x,y〉 is cyclic for all y∈G} and x is adjacent y if 〈x,y〉 is not a cyclic subgroup. They established some graph theoretical properties (such as regularity) of this graph in terms of the group ones.In this paper, we consider the converse. We associate a graphΓG with G (called the cyclic graph of G) as follows: take G as the vertices of ΓG and two distinct vertices x and y are adjacent if and only if 〈x,y〉 is a cyclic subgroup of G. For example, Figure 1 is the cyclic graph of Z2×Z2, and Figure 2 is ΓS3. For any group G, it is easy to see that the cyclic graph ΓG is simple and undirected with no loops and multiple edges. By the definition, we shall explore how the graph theoretical properties of ΓG affect the group theoretical properties of G. In particular, the structure of the group by some graph theoretical properties of the associated graph is determined.Figure 1
Γ
Z
2
×
Z
2.Figure 2
Γ
S
3.The outline of this paper is as follows. In Section2, we introduce a lot of basic concepts and notations of group and graph theory which will be used in the sequel. In Section 3, we give some properties of the cyclic graph of a group on diameter, planarity, partition, clique number, and so forth and characterize a finite group whose cyclic graph is complete (planar, a star, regular, etc.). For example, the cyclic graph of any group is always connected whose diameter is at most 2 and the girth is either 3 or ∞; the cyclic graph ΓG of group G is complete if and only if G is cyclic and is a star if and only if G is an elementary abelian 2-group. In particular, for a finite group G, Aut(ΓG)=Aut(G) if and only if G≅Z2×Z2, the Klein group. In Section 4, we present some properties of the cyclic graphs of the dihedral groups D2n, including degrees of vertices, traversability (Eulerian and Hamiltonian), planarity, coloring, and the number of edges and cliques. Furthermore, we get the automorphism group of D2n for all n≥3. Particularly, for all n>2, if G is a group with ΓG≅ΓD2n, then G≅D2n. Similar to Section 4, we discuss the properties of the cyclic graphs on the generalized quaternion groups Q4n in Section 5. In Section 6, we obtain some parameters on the cyclic graphs of finite noncyclic groups of order up to 14.


## 2. Preliminaries

In this paper, we consider simple graphs which are undirected, with no loops or multiple edges. LetΓ be a graph. We will denote V(Γ) and E(Γ) the set of vertices and edges of Γ, respectively. Γ is, respectively called empty and complete if V(Γ) is empty and every two distinct vertices in V(Γ) are adjacent. A complete graph of order n is denoted by Kn. The degree of a vertex v in Γ, denoted by degΓ(v), is the number of edges which are incident to v. A subset Ω of V(Γ) is called a clique if the induced subgraph of Ω is complete. The order of the largest clique in Γ is its clique number, which is denoted by ω(Γ). A k-vertex coloring of Γ is an assignment of k colors to the vertices of Γ such that no two adjacent vertices have the same color. The chromatic number χ(Γ) of Γ is the minimum k for which Γ has a k-vertex coloring. If u,v∈V(Γ), then d(u,v) denotes the length of the shortest path between u and v. The largest distance between all pairs of V(Γ) is called the diameter of Γ and denoted by diam(Γ). The length of the shortest cycle in the graph Γ is called girth of Γ; if Γ does not contain any cycles, then its girth is defined to be infinity (∞). For a vertex v of Γ, denote by NΓ(v) the set of vertices in Γ which are adjacent to v. A vertex v of Γ is a cutvertex if Γ-{v} is disconnected. An x-y path of length d(x,y) is called an x-y geodesic; the closed interval I[x,y] of x and y is the set of those vertices belonging to at least one x-y geodesic. A set U of V(Γ) is called a geodetic set for Γ if I[U]=V(Γ), where I[U]=⋃x,y∈U‍I[x,y]. A geodetic set of minimum cardinality in Γ is called a minimum geodetic set and this cardinality is the geodetic number. A set S of vertices of Γ is a dominating set of Γ if every vertex in V(Γ)∖S is adjacent to some vertex in S; the cardinality of a minimum dominating set is called the domination number of Γ and is denoted by γ(Γ). Γ is a bipartite graph means that V(Γ) can be partitioned into two subsets U and W, called partite sets, such that every edge of Γ joins a vertex of U and a vertex of W. If every vertex of U is adjacent to every vertex of W, Γ is called a complete bipartite graph, where U and W are independent. A complete bipartite graph with |U|=s and |W|=t is denoted by Ks,t. For more information, the reader can refer to [5].In this paper, all groups considered are finite. LetG be a finite group with identity element e. The number of elements of G is called its order and is denoted by |G|. The order of an element x of G is the smallest positive integer n such that xn=e. The order of an element x is denoted by |x|. For more notations and terminologies in group theory consult [6].


## 3. Some Properties of the Cyclic Graphs

Definition 1.
In group theory, a locally cyclic group is a group in which every finitely generalized subgroup is cyclic. A group is locally cyclic if and only if every pair of elements in the group generates a cyclic group. It is a fact that every finitely generalized locally cyclic group is cyclic. So a finite locally cyclic group is cyclic.Definition 2 (see [7, 8]).
LetG be a group. The cyclicizer of an element x of G, denoted CycG(x), is defined by
(1)CycG(x)={y∈G∣〈x,y〉iscyclic}.
In general, the cyclicizer CycG(x) of x is not a subgroup of G. For example, let G=Z4×Z2, then CycG((2,0))={(0,0),(1,0),(1,1),(2,0),(3,0),(3,1)} is not a subgroup.Definition 3.
The cyclicizerCyc(G) of G is defined as follows:
(2)Cyc(G)=⋂x∈G‍CycG(x)={y∈G∣〈x,y〉iscyclic∀x∈G}.
By [9, Theorem 1], Cyc(G) is a normal subgroup of G and Cyc(G)≤Z(G).Definition 4.
LetG be a group. The cyclic graph ΓG of G is a graph with V(ΓG)=G and two distinct vertices x,y are adjacent in ΓG if and only if 〈x,y〉 is a cyclic subgroup of G.Proposition 5.
For any groupG, degΓG(x)=|CycG(x)|-1, where x∈G.Proof.
By Definitions2 and 4, it is straightforward.Proposition 6.
LetG be a group with the identity element e. Then diam(ΓG)≤2. In particular, ΓG is connected and the girth of ΓG is either 3 or ∞.Proof.
Suppose thatx and y are two distinct vertices of ΓG. If 〈x,y〉 is a cyclic subgroup of G, then x is adjacent to y, and hence d(x,y)=1. Thus we may assume that 〈x,y〉 is not cyclic. Note that both 〈e,x〉 and 〈e,y〉 are cyclic and the vertices x and y are adjacent to e; hence we get d(x,y)=2. This means that ΓG is connected and diam(ΓG)≤2. If there exist x≠e,y≠e such that x and y are joined by some edge, then {x,y,e} is a cycle of order 3 of ΓG and so the girth of ΓG is 3. Otherwise, every two vertices (nonidentity elements of G) of ΓG are not adjacent; that is, ΓG is a star, which implies that the girth of ΓG is equal to ∞.The following proposition is obvious; we omit its proof.Proposition 7.
LetG be a group with |G|>2. Then {e} is a dominating set of order 1 of ΓG. In particular, γ(ΓG)=1 and degΓG(e)=|G|-1.Corollary 8.
LetG be a group. Then {x} is a dominating set if and only if x∈Cyc(G). Moreover, the number of the dominating sets of size 1 is |Cyc(G)|.Theorem 9.
LetG be a nontrivial group. Then diam(ΓG)=1 (or equivalently ΓG is complete) if and only if G is a cyclic group.Proof.
Letx and y be two arbitrary elements of G. Suppose that diam(ΓG)=1. Then 〈x,y〉 is a cyclic subgroup of G. By Definition 1, G is a cyclic group as G is finite. For the converse, if G is a cyclic group, then 〈x,y〉 is a cyclic subgroup of G. Thus diam(ΓG)=1, as desired.Corollary 10.
LetG be noncyclic group. Then ΓG is not regular.Theorem 11.
LetG be a group with the identity element e. Then ΓG≅K1,|G|-1 (or equivalently ΓG is a star) if and only if G is an elementary abelian 2-group.Proof.
Assume thatΓG is a star. Let x be a nonidentity element of G. If |x|≥3, then x and x-1 are adjacent since 〈x,x-1〉 is a cyclic subgroup of G, which is contrary to ΓG being a star. Hence |x|=2. It follows that the order of every element of G is 2. If x and y are two elements of G, then (xy)2=xyxy=xxyy=e, and hence xy=yx. It means that G is an abelian group and exp(G)=2. It follows that G is an elementary abelian 2-group.
Conversely, suppose thatG is an elementary abelian 2-group. Then the order of every cyclic subgroup of G is 2. Let x is a nonidentity element of G. If there exists an element y such that 〈x,y〉 is cyclic, then 〈x,y〉=〈x〉, which implies y∈〈x〉. Note that x is an element of order 2; then y=e as x≠y. It follows that the unique element e is adjacent to x in ΓG. So ΓG≅K1,|G|-1.Corollary 12.
LetG be an elementary abelian 2-group. Then Aut(ΓG) is isomorphic to the symmetric S|G|-1 on |G|-1 letters.Corollary 13.
LetG be group. Then ΓG is a tree if and only if G is an elementary abelian 2-group.Corollary 14.
LetG be group with |G|>2. If ΓG is bipartite, then Cyc(G)={e}.Proof.
Assume, on the contrary,Cyc(G)≠{e}. Then there exist two adjacent vertices x and y such that x,y∈Cyc(G). Since |G|>2, there is an element z such that z≠x,z≠y. By Definition 3, {x,y,z} is a cycle of length 3 and so the subgraph of ΓG induced by {x,y,z} is an odd cycle, which is a contradiction to ΓG being bipartite (see [5, Theorem 1.12, page 22]).Remark 15.
LetG=Z2. Then ΓG is a bipartite graph, while Cyc(G)≠{e}.Corollary 16.
LetG be group. Then ΓG is bipartite if and only if G is an elementary abelian 2-group.Proposition 17.
LetG1 and G2 be two groups. If G1≅G2, then ΓG1≅ΓG2.Proof.
Letϕ be an isomorphism from G1 to G2. Obviously, ϕ is a one-to-one correspondence between ΓG1 and ΓG2. Let x and y be two vertices of ΓG1. If 〈x,y〉=〈g〉 is cyclic, then there exist two positive integers n,m such that x=gn and y=gm, so xϕ=(gϕ)n and yϕ=(gϕ)m; It means that xϕ,yϕ∈〈gϕ〉, that is, 〈xϕ,yϕ〉 is a subgroup of 〈gϕ〉. Thus 〈xϕ,yϕ〉 is cyclic. Note that ϕ is invertible. It follows that x and y are adjacent in ΓG1 if and only if xϕ is adjacent to yϕ in ΓG2. Consequently, ϕ is a graph automorphism from ΓG1 to ΓG2, namely, ΓG1≅ΓG2.Remark 18.
The converse of Proposition17 is not true in general. Let G1 be the modular group of order 16 (a group is called a modular group if its lattice of subgroups is modular) with presentation
(3)〈s,t:s8=r2=e,st=ts5〉.
Clearly, G1={sktm∣k=0,1,…,7,m=0,1}. Let G2=Z2×Z8. For G1, this is the same subgroup lattice structure as for the lattice of subgroups of G2. It is easy to see that ΓG1≅ΓG2, however, G1≇G2 because G1 is not abelian.Theorem 19.
LetG be a group and let a be an element of G. If |g|≤|a| for all g∈G, then ω(ΓG)=|a|.Proof.
Let|a|=n. Then the induced subgraph of {a,a2,…,an-1,e} is complete; hence {a,a2,…,an-1,e} is a clique of ΓG. On the other hand, if ω(ΓG)=m, then there exists a subset C of V(ΓG) such that the subgraph of ΓG induced by C is complete and |C|=m. Note that the order of the largest clique is m; e must be an element of C. If x∈C, then we have 〈x,g〉 being cyclic for every g in C∖{x}. Clearly 〈x,g〉=〈x-1,g〉; that is, x-1∈C. Let x,y be two arbitrary elements of C. So 〈x,y〉 is cyclic. Since 〈xy,x〉≤〈x,y〉 and 〈xy,y〉≤〈x,y〉, xy and x are adjacent in ΓG; yet, xy is adjacent to y. Suppose z∈C∖{x,y}, it is easy to see that 〈xy,z〉≤〈x,y,z〉. Since 〈x,y,z〉 is a locally cyclic group by Definition 1, 〈x,y,z〉 is a cyclic group; namely, 〈xy,z〉 is cyclic. Consequently, xy and z are joined by an edge of ΓG. From what we have mentioned above, we can see that C is a group of G. Again, C is a cyclic subgroup of G by Definition 1. Let C=〈b〉, where b is an element of G. It follows that |b|≤|a| from the hypothesis; that is, ω(ΓG)=|a|.Corollary 20.
LetG be group. If C={x,x2,…,x|x|-1,e}=〈x〉, then C is a clique of ΓG. Converse holds only when C is the largest clique.Corollary 21.
Letn≥3. Then Sn and An are planar if and only if n=3 or 4.Theorem 22.
LetG be a group. Then degΓG(x)=|x|-1 for all x∈V(ΓG)∖{e} if and only if every element of G∖{e} is of prime order.Proof.
Assume thatdegΓG(x)=|x|-1 for every nonidentity element x of G. If there exists an element x of G∖{e} such that x is not of prime order, then we may choose t such that t divides the order of x and 1<t<|x|. Thus xt≠e and x is adjacent to xt, since 〈x,xt〉=〈x〉. while x∉〈xt〉 (otherwise, 〈x〉=〈xt〉, a contradiction). so NΓG(xt)={x}∪(〈xt〉∖{xt}). This is contrary to degΓG(xt)=|xt|-1.
For the converse, suppose every nonidentity elementx of G is of prime order. If 〈x,y〉 is a cyclic subgroup of G, then |〈x,y〉| is a prime number. Thereby, 〈x,y〉=〈x〉, and so y∈〈x〉. That is, CycG(x)=〈x〉. Hence the theorem follows.Theorem 23.
LetG be a group. Then NΓG(x)∪{x} is a cyclic subgroup for all x∈G∖{e} if and only if every element x of G∖{e} is contained in precisely one maximal cyclic subgroup of G.Proof.
Assume that every element ofG∖{e} is contained in exactly one maximal cyclic subgroup of G. If x is an element of G∖{e}, then there is a maximal cyclic subgroup 〈y〉 such that x∈〈y〉. Let a∈CycG(x). Since 〈x,a〉 is cyclic, 〈x,a〉=〈z〉. If 〈x,a〉⩽〈y〉, then there exists a maximal cyclic subgroup 〈w〉 such that z∈〈w〉 as z≠e. However x∈〈w〉; this gives a contradiction to 〈y〉 being the precisely one maximal cyclic subgroup of containing x. Consequently 〈x,a〉≤〈y〉, and so a∈〈y〉. Also, if b∈〈y〉, then 〈x,b〉≤〈y〉, so x and b are adjacent in ΓG; it means that b∈CycG(x). Thus CycG(x)=〈y〉; that is, CycG(x) is cyclic. In other words, NΓG(x)∪{x} is a cyclic subgroup of G.
Conversely, letx be an element of G∖{e} such that x∈〈y〉 and x∈〈z〉, where 〈y〉 and 〈z〉 are two maximal cyclic subgroups of G. Assume that NΓG(x)∪{x} is cyclic. Since x is adjacent to y, we have 〈y〉≤NΓG(x)∪{x}, so 〈y〉=NΓG(x)∪{x}. Similarly, 〈z〉=NΓG(x)∪{x}, and thus 〈y〉=〈z〉; that is, x is contained in precisely one maximal cyclic subgroup of G.Theorem 24.
LetG be a group. Then Aut(ΓG)=Aut(G) if and only if G is isomorphic to the Klein group Z2×Z2.Proof.
First we suppose thatAut(ΓG)=Aut(G) for group G. We shall show that G is isomorphic to the Klein group Z2×Z2 by the following steps.
Step  1 (
G
is abelian). Let ψ be an automorphism of ΓG. Then ψ is an automorphism of group G, so (xy)ψ=xψyψ for all x,y∈G. Now we define the mapping α: xα=x-1 for all x in V(ΓG). It is well known that α is a bijection and 〈a,b〉 is cyclic if and only if 〈a-1,b-1〉 is cyclic; that is, ab is an edge of ΓG if and only if aαbα is an edge of ΓG. Thus α∈Aut(ΓG). By hypothesis, α∈Aut(G), so (xy)α=xαyα=(xy)-1=y-1x-1=x-1y-1 for all x,y∈G; namely, xy=yx, and hence G is a abelian group.
Step  2 (
G
is not a cyclic group). If G is a cyclic group, then we can see that ΓG is isomorphic to the complete graph K|G| by Theorem 9, and hence Aut(ΓG) is isomorphic to the symmetric group S|G|. Since |G|≥3 (if |G|=2, then Aut(G)={e}, but Aut(ΓG)≅Z2, a contradiction), Aut(ΓG) is nonabelian. However, Aut(G) must be abelian as G is cyclic, a contradiction.
Step  3 (
G
is an elementary abelian 2-group). By Step 1, we have G=〈a1〉×〈a2〉×⋯×〈ar〉, where |ai|∣|ai+1| for all i=1,2,…,r-1. It is clear that r>1 by Step 2. Obviously, there exists a graph automorphism ψ such that a1ψ=a1,arψ=ar,(a1ar)ψ=(a1ar)-1, and ((a1ar)-1)ψ=a1ar. Since Aut(ΓG)=Aut(G), we have ψ∈Aut(G) and (a1ar)ψ=a1ψarψ. It follows that a12=ar-2∈〈a1〉∩〈ar〉={e}. Furthermore, |a1|=|ar|=2. In particular, |a2|=|a3|=⋯=|ar-1|=2. It follows that G is an elementary abelian 2-group.
Step  4 (finishing the proof). Let |G|=2n for some positive integer n. By Step 3 and Theorem 11, ΓG is isomorphic to the star K1,2n-1. So Aut(ΓG) is the symmetric group S2n-1 of degree 2n-1, while Aut(G) is isomorphic to the general linear group GL(n,2). Thus n=2 as Aut(ΓG)=Aut(G). That is, G≅Z2×Z2.
For the converse, we suppose thatG≅Z2×Z2. Then we have Aut(G)=S3. On the other hand, ΓG≅K1,3, and so Aut(ΓG)=Aut(G)=S3.Remark 25.
SupposeG=Z2×Z2, then ΓG≅K1,3. Let Z2×Z2={e,a,b,ab∣a2=b2=e,ab=ba}. Then |Aut(G)|=6, more specifically,
(4)φ1={a↦a,b↦ab,ab↦b,e↦e,φ2={a↦b,b↦ab,ab↦a,e↦e,φ3={a↦ab,b↦b,ab↦b,e↦e,φ4={a↦b,b↦a,ab↦ab,e↦e,φ5={a↦ab,b↦a,ab↦b,e↦e,φ6=e,
here φi∈Aut(G) for i=1,2,…,6. Clearly, we can see that Aut(G) is nonabelian; that is, Aut(G)≅S3.Proposition 26.
LetG be an elementary abelian p-group for some prime integer p. Then ΓG is isomorphic to Figure 3.Figure 3
The cyclic graph of the elementary abelianp-group.Proof.
Letx be an element of G and x≠e. Since G is an elementary abelian p-group, we conclude that the order of x is p. It follows that the subgraph of ΓG induced by {x,x2,…,xp-1} is isomorphic to the complete graph Kp-1 of order p-1. Let y be an element such that y∉〈x〉. If x and y are adjacent, then 〈x,y〉 is a cyclic subgroup of G, which implies 〈x,y〉=〈x〉=〈y〉 since 〈x,y〉 is a cyclic subgroup of order 5, and this gives a contradiction to y∉〈x〉. Thus x is uniquely adjacent to every vertex of {e,x,x2,…,xp-1}. This completes the proof.Remark 27.
Letp be composite. Then, in general, Zp×Zp×⋯×Zp is not isomorphic to Figure 3. For example, let G=Z4×Z4, then degΓG((2,0))=5>4. In fact, NΓG((2,0))={(1,2),(0,0),(3,2),(1,0),(3,0)}.


## 4. The Cyclic Graphs of the Dihedral Groups

Forn≥3, the dihedral group D2n is an important example of finite groups. As is well known, D2n=〈r,s:s2=rn=e,s-1rs=r-1〉. As a list,
(5)D2n={r1,r2,…,rn=e,sr1,sr2,…,srn}.Theorem 28.
LetΓD2n be the cyclic graph of D2n and n≥3. Then(1)
degΓD2n(sri)=1 for any 1≤i≤n;(2)
degΓD2n(ri)=n-1 for any 1≤i<n;(3)
ΓD2n is not Eulerian;(4)
ΓD2n is not Hamiltonian;(5)
ΓD2n is planar if and only if n=3 or 4;(6)
ΓD2n is a split graph;(7)
Aut(ΓD2n)≅Sn×Sn-1.Proof.
(1) Clearly, the order ofsri is 2 for all 1≤i≤n by the definition of D2n. Since every cyclic subgroup of G has a uniquely cyclic subgroup of order 2, 〈sri,srj〉 is noncyclic; that is, sri and srj are not adjacent to each other. If sri is adjacent to rj, where j≠n, then 〈sri,rj〉 is cyclic and hence 〈sri,rj〉=〈rk〉, which is a contradiction. Thus, e is the unique element of G which is adjacent to sri, as required.
(2) It is easy to see thatdegΓD2n(ri)≥n-1 for any 1≤i<n. Now (1) completes the proof.
(3) SincedegΓD2n(s) is an odd integer by (1), ΓD2n is not Eulerian (see [5, Theorem 6.1, page 137]).
(4) In view of (1) and (2),ΓD2n contains a cut-vertex e. In the light of [5, Theorem 6.5, page 145], we conclude that ΓD2n cannot be Hamiltonian.
(5) Ifn=3 or 4, then it is easy to see that ΓD2n is planar. Now suppose that ΓD2n is planar. Since the complete graph of order 5 is not planar, we have ω(ΓD2n)<5. Since the subgraph of ΓD2n induced by {r,r2,…,rn-1,rn} is complete, we have n<5. That is, n=3 or 4, as desired.
(6) By (1) and (2), the vertex set ofΓD2n can be partitioned into the clique {r,r2,…,rn-1,e} and the independent set {sr1,sr2,…,srn-1,s}, and hence ΓD2n is a split graph.
(7) It is straightforward.Corollary 29.
LetΓD2n be the cyclic graph of D2n and n≥3. Then ΓD2n is not bipartite.Corollary 30.
Letn≥3. Then |E(ΓD2n)|=n(n+1)/2.Corollary 31.
Letn≥3. Then ω(ΓD2n)=χ(ΓD2n)=n.Theorem 32.
Letn>2 be an integer. If G is a group with ΓG≅ΓD2n, then G≅D2n.Proof.
We have|G|=2n by Definition 4. In view of Theorem 28, we can see that ω(ΓG)=n. It follows from Theorem 19 that there exists an element r∈G such that 〈r〉 is a cyclic subgroup of order n. Note that |G:〈r〉|=2; we have 〈r〉 being a normal subgroup of G. Since there are n vertices in ΓG such that the degrees equal 1, there exist n elements of order 2 in G. Now we choose an involution s of order 2 of G such that s∉〈r〉. It is easy to see that G=〈r〉⋊〈s〉; that is, G≅Zn⋊Z2. By the definition of dihedral group, Z2 acts on Zn by inversion. This implies that G≅D2n, as required.


## 5. The Cyclic Graphs of the Generalized Quaternion Groups

The quaternion groupQ8 is also an important example of finite nonabelian groups; it is given by
(6)Q8=〈-1,i,j,k:(-1)2=1,i2=j2=k2=ijk=-1〉.As a generalization ofQ8, the generalized quaternion group Q4n is defined as
(7)Q4n=〈a,b:b2=an,a2n=e,bab-1=a-1〉,
where e is the identity element and n≥2 (if n=2, then Q4n=Q8). Clearly, Q4n has order 4n as a list
(8)Q4n={a,a2,…,a2n-1,e,b,ab,…,a2n-1b}.
Moreover, Z(Q4n)={e,an} and |aib|=4, where 1≤i≤2n.Lemma 33.
C
y
c
(
Q
4
n
)
=
{
e
,
a
n
}.Proof.
Since(aib)2=b2=an and |aib|=4 for all i, 〈aib,an〉=〈aib〉; that is, an∈CycQ4n(aib) for all i. On the other hand, it is obvious that 〈aj,an〉 is a cyclic subgroup of Q4n for all j as 〈aj,an〉≤〈a〉, where 1≤j≤2n. Consequently an∈CycQ4n(aj) for all j, namely, an∈Cyc(Q4n). However, Cyc(Q4n)⊆Z(Q4n), so Cyc(Q4n)=Z(Q4n)={e,an}.Proposition 34.
LetΓQ4n be the cyclic graph of Q4n. Then(1)
degQ4n(aib)=3 for all 1≤i≤2n;(2)
degQ4n(aj)=2n-1 for all 1≤j<n and n<j<2n;(3)
degQ4n(e)=degQ4n(an)=4n-1.Proof.
(1) Since|aib|=4 for all 1≤i≤2n, degQ4n(aib)≥3. Obviously, {e,an,(aib)-1}⊆NΓQ4n(aib). If aib and ajb are joined by an edge, then 〈aib,ajb〉 is a cyclic subgroup of order 4; Note that 〈aib〉 is a cyclic subgroup of order 4, then aib=ajb or aib=(ajb)-1. On the other hand, it is easy to see that 〈aib,aj〉 cannot be cyclic, where 1≤j<n and n<j<2n. Consequently, we have {e,an,(aib)-1}=NΓQ4n(aib), and so degQ4n(aib)=3.
(2) By the proof of (1), we see that〈aib,aj〉 is not cyclic for all 1≤j<n and n<j<2n, so degQ4n(aj)=2n-1.
(3) Obviously by Lemma33.Corollary 35.
Letn≥2. Then |E(ΓD4n)|=2n2+4n.Corollary 36.
Letn≥2. Then ω(ΓD4n)=χ(ΓD4n)=2n.Theorem 37.
LetΓQ4n be the cyclic graph of Q4n. Then ΓQ4n is planar if and only if n=2.Proof.
Supposen=2. It is easy to see that ΓQ8 is planar. Now assume that ΓQ4n is a planar graph. Then ω(ΓD2n)<5 since K5 is nonplanar. By Theorem 19, there exists no the element g of Q4n such that |g|≥5. However |a|=2n, and hence n=2.Theorem 38.
LetΓQ4n be the cyclic graph of Q4n and n≥2. Then(1)
ΓQ4n is not Eulerian;(2)
ΓQ4n is not Hamiltonian.Proof.
(1) It is similar to the proof of (3) in Theorem28.
(2) Letk(ΓQ4n) denote the number of components in the graph ΓQ4n. By Theorem 6.5 of [5] on page 145, if ΓQ4n is Hamiltonian, then for every nonempty proper set S of vertices of ΓQ4n, we have k(ΓQ4n-S)≤|S|. Now suppose S={e,an}. Then the number of components of the resulting graph ΓQ4n-S is equal to n+1. However, n+1>|S|, a contradiction.


## 6. The Cyclic Graphs of Noncyclic Groups of Order up to 14

It is significant to obtain detailed information on the cyclic graphs of some noncyclic groups of lower order. In this section, we present a table on the cyclic graphs of noncyclic groups of order up to14, as shown in Table 1.Table 1
Cyclic  graph
Isomorphic graph
Vertex degree sequences
Clique number
Geodetic  number
Planarity
Γ
Z
2
×
Z
2
K
1,3
3, 1, 1, 1
2
3
Planar
Γ
S
3
5, 2, 2, 1, 1, 1
3
5
Planar
Γ
Z
2
×
Z
2
×
Z
2
K
1,7
7, 1, 1, 1, 1, 1, 1, 1
2
7
Planar
Γ
Z
2
×
Z
4
7, 5, 3, 3, 3, 3, 1, 1
4
6
Planar
Γ
D
8
7, 3, 3, 3, 1, 1, 1, 1
4
7
Planar
Γ
Q
8
7, 7, 3, 3, 3, 3, 3, 3
4
6
Planar
Γ
Z
3
×
Z
3
8, 2, 2, 2, 2, 2, 2, 2, 2
3
8
Planar
Γ
D
10
9, 4, 4, 4, 4, 1, 1, 1, 1, 1
5
9
Nonplanar
Γ
Z
2
×
Z
6
11, 9, 9, 5, 5, 5, 3, 3, 3, 3, 1, 1
6
10
Nonplanar
Γ
D
12
11, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1
6
11
Nonplanar
Γ
Q
4
×
3
11, 11, 5, 5, 5, 5, 3, 3, 3, 3, 3,  3
6
10
Nonplanar
Γ
A
4
11, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1
3
11
Planar
Γ
D
14
13, 6, 6, 6, 6, 6, 6, 1, 1, 1, 1, 1,  1, 1
7
13
Nonplanar



---

*Source: 107265-2013-04-16.xml*