Commuting Graphs Of Dihedral Type Groups
Zahid Raza
y, Shahzad Faizi
zReceived 4 July 2013
Abstract
For a non-abelian group G and a subset X of G, we de…ne the commuting graph, denoted (X) =C(G; X), to be the graph whose vertex set isX with two distinct verticesx; y2X joined by an edge if and only ifxy=yx.
In this short note, certain properties of commuting graphs constructed on the dihedral type groups D2n with respect to some speci…c subsets are discussed.
More precisely, the chromatic number and clique number of these commuting graphs are obtained.
1 Introduction
The study of algebraic structures, using the properties of graphs, has become an ex- citing research topic in the last twenty years, leading to many fascinating results and raising questions. For example, the study of zero-divisor graphs [6], total graph of commutative rings and commuting graph of groups has attracted many researchers towards this dimension. The concept of non-commuting graph has been studied in [2]
and [16]. Recently, the commuting graphs of groups have been studied extensively, see for example [5, 15–17], and those of rings in [3–4]. In [15], Iranmanesh and Jafarzadeh conjectured that there is a universal upper bound on the diameter of a connected commuting graph for any …nite nonabelian group. They determined that when the commuting graph of a symmetric or alternating group is connected and that the diam- eter is at most5 in this case. The paper [17] proves that for all …nite classical simple groups over a …eld of size at least5, when the commuting graph of a group is connected then its diameter is at most10.
If X is a conjugacy class of involutions of a group G, then (G; X) is called a commuting involution graph. Aschbacher [1] also showed a necessary condition on a commuting involution graph for the presence of a strongly embedded subgroup in G.
The detailed study of commuting involution graphs can be found in [7–10, 13–15].
In this informative note, we discuss certain properties of commuting graphs con- structed on the dihedral type groups D2n with respect to some speci…c subsets. For ordinary dihedral groupD2n, the commuting graph of dihedral groupD2nwas discussed in [11].
Mathematics Sub ject Classi…cations: 05C12.
yDepartment of Mathematics, National University of Computer & Emerging Sciences Lahore Cam- pus, B-Block, Faisal Town, Lahore, Pakistan.
zDepartment of Mathematics, National University of Computer & Emerging Sciences Lahore Cam- pus, B-Block, Faisal Town, Lahore, Pakistan.
221
2 De…nitions and Notations
We consider simple graphs which are undirected, with no loops or multiple edges. For any graph , we denote the set of the vertices and edges of by V( ) and E( ), respectively. The degree deg(v)of a vertexv in is the number of edges incident to v. A graph is regular if the degrees of all the vertices of are same.
A subsetX of the vertices of is called a clique if the induced subgraph ofX is a complete graph. The maximum size of a clique in a graph is called the clique number of and denoted byw( ).
Let k >0 be an integer. A k-vertex coloring of a graph is an assignment of k colors to the vertices of such that no two adjacent vertices receive the same color.
The chromatic number ( )of a graph , is the minimumkfor which has ak-vertex coloring.
If uand v are vertices in , thend(u; v) denotes the length of the shortest path betweenuandv. The maximum distance between all pairs of the vertices of is called the diameter of , and is denoted by diam( ).
A matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices.
A perfect matching is a matching which matches all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching.
A subsetXof the vertices of is called an independent set if the induced subgraph onXhas no edge. The independent number of is the maximum size of an independent set of vertices and is denoted by ( ).
A vertex cover of a graph is a setS V( )that contains at least one endpoint of every edge. The minimum size of a vertex cover is denoted by ( ).
3 Group Properties of D
2nThe dihedral type groups denoted by D2n, are de…ned in terms of generators a; band relations as: D2n =< a; b j bn=a2= 1; ab=bra >;where n= 4k withr= 2k 1 or r = 2k+ 1and any positive integer k 2:In this section, we discuss some of the group theoretic properties of the group D2n. Throughout this note a; brepresent the abstract generators of the groupsD2n and n; m; d; rare always positive integers.
LEMMA 1. Ifaandbare the abstract generators of the groupsD2n;then we have the followings:
(i) a(bma) =bmr for allm < n,
(ii) (bma)2l=b(r+1)lm for allm < nand any positive integerl,
(iii) (bma)2l 1=b(l 1)mr+lmafor allm < nand any positive integerl.
Note: Lemma 1 shows that the order ofbmamust be even. The following Lemmas are easy to proof, so we will give only statements:
LEMMA 2. Ifn= 4k andr= 2k 1, thengcd(n; r 1)is either2,4or n2. LEMMA 3. The elementbiis in the center of the groupD2nif and only ifnj(r 1)i, where i6= 1.
LEMMA 4. Consider the groupD2n. We have the following results:
(i) Ifgcd(n; r 1) =d, then there aredcentral elements ofD2n. More precisely, Z(D2n) =fbnd; b2nd; b3nd; : : : ; bng:
(ii) The element bia will commute with all the elementsbja, where1 j n 1 if and only ifnj(r 1)(j i)for …xedi.
(iii) Ifgcd(n; r 1) =d, then[D2n :Z(D2n)] = 2nd:
4 Commuting Graph of D
2nLet[G:Z(G)] =mandT =f1; x1; x2: : : ; xm 1g be a transversal ofZ(G)in a group G. It is clear that every two elements of the cosetxiZ(G),1 i m 1, commute.
Thus, every two elements of these coset are adjacent. Throughout this section, we shall denote X1=fb1; b2; b3; : : : ; bng andX2=fb1a; b2a; b3a; : : : ; bnag two subsets ofD2n.
We associate to the commuting graph (D2n) = C(D2n; D2n) of the group D2n, the induced subgraph u(D2n)as follows: The vertex set of u(D2n)isU =T f1g= fx1; x2: : : ; xm 1g, and two verticesxi andxj are adjacent if and only ifxixj=xjxi, where 1 i; j m 1.
LEMMA 5. IfX is any subset of D2n and (X) =C(D2n; X) is the commuting graph onX, then for anya2X,deg(a) =jCX(a)j 1:
LEMMA 6. If (D2n) =C(D2n; D2n), then
(1) deg(bma) = 8<
:
3 if gcd(n; r 1) = 2;
7 if gcd(n; r 1) = 4;
n 1 if gcd(n; r 1) = n2: (2) deg(bi) = 2n 1 ifnj(r 1)i;
n 1 otherwise.
PROOF. (1) Ifgcd(n; r 1) = 2, then there are two central elementseandbn2. Now, we haveCbma =fe; bn2; bma; bm+n2ag for allbma2D2n. Hence by virtue of Lemma 5 we have,deg(bma) = 4 1 = 3. The remaining case can be proof in a similar manner.
(2) Ifnj(r 1)i, then by Lemma 3, we haveCbi =D2n and sodeg(bi) = 2n 1.
Ifn-(r 1)i, then Cbi =fbj: 1 j ngand so deg(bi) =n 1.
COROLLARY 1. IfX =D2nnZ(D2n)and (X) =C(D2n; X)is the commuting graph onX, then
(1) deg(bma) = 8<
:
1 if gcd(n; r 1) = 2;
3 if gcd(n; r 1) = 4;
n
2 1 if gcd(n; r 1) = n2: (2) deg(bi) =
8<
:
n 3 if gcd(n; r 1) = 2;
n 5 if gcd(n; r 1) = 4;
n
2 1 if gcd(n; r 1) = n2:
(3) If (X) =C(D2n; X), where X=D2nnZ(D2n), thendiam( (X)) =1:
LEMMA 7. IfX is any subset ofD2n, then (X) =Kn if and only ifX =X1. PROOF. SupposeX =fbi: 1 6i6ng. ThenX is a cyclic subgroup ofD2n and so (X)is a complete graph of nvertices. Conversely, Suppose (X) =Kn. Then by Lemma 5, we have X=fbi: 16i6ng=X1.
COROLLARY 2. There does not exist any subset X of D2n such that (X)is n regular.
PROPOSITION 1. IfX=D2n, then the edges in the commuting graph (X)are:
jE( (D2n))j= 8>
<
>:
n(n+4)
2 if gcd(n; r 1) = 2;
n(n+10)
2 if gcd(n; r 1) = 4;
n(5n 4)
4 if gcd(n; r 1) = n2: PROOF. Note thatX1T
X2=;andX1S
X2= D2n. Suppose thatgcd(n; r 1) = 2. Then the subgraph induced byX1 is complete and the subgraph induced by X2 is
n
2K2. Therefore the number of edges in (D2n)is the sum of the number of edges in these subgraphs and the number of edges from the center elementsbn andbn2 to the set of vertices in the induced graph byX2. ThusE( (D2n)) = n(n2 1)+n2+ 2n= n(n+4)2 . Similarly one can prove the remaining cases.
COROLLARY 3. If (X) =C(D2n; X), whereX =D2nnZ(D2n), then
jE( (D2n))j= 8>
<
>:
n2 4n+6
2 if gcd(n; r 1) = 2;
n2 6n+20
2 if gcd(n; r 1) = 4;
3n(n 2)
8 if gcd(n; r 1) = n2: THEOREM 1. There exists no subsetX ofD2n such that (X) =C4.
PROOF. Letgcd(n; r 1) = 2and suppose (X) =C4 for some subsetX ofD2n. Then (X)contains a complete graph of typeKninX1and n2 complete graphs of type K2inX2. IfX contains two vertices ofX2from di¤erentK2and two vertices fromX1. Then this graph has no edge between the elements from di¤erentK2, a contradiction.
SupposeX contains two elements from any one ofK2inX2and two elements fromX1 and they could be either one or both central elements. Then in both cases, the degree of vertex of the central element is 3 and hence we get a contradiction. If X contains any3elements fromX1and one element from anyK2inX2then the graph contains a complete graph of typeK3 in X1 and thus a contradiction. Similarly ifX X1 then (X)is an induced subgraph of a complete graph (X1)and hence itself complete, a contradiction again. Similarly one can prove the remaining cases.
The following Lemma can be proof in a similar fashion as Theorem 1:
LEMMA 8. There exist no subsetX ofD2n such that (X) =P4.
THEOREM 2. If (D2n) is the commuting graph on D2n, then w( (D2n)) = ( (D2n)) =n.
PROOF. SinceX1 =fb1; b2; b3; : : : ; bng D2n and (X1)is a maximal complete subgraph of (D2n). Hencew( (D2n)) =n:
Ifgcd(n; r 1) = 2, then we needncolors to color the induced subgraph (X1) (D2n) and so ( (D2n)) n. Note that e and bn2 are two central elements in X1
and they are adjacent to all vertices in (D2n)and so color assigned to these vertices cannot be assigned to any other vertices. The remaining n 2 vertices inX1 are not adjacent to any of the remaining vertices in (D2n)and so these vertices can be colored by any one of the remaining n 2 colors. Hence ( (D2n)) = n. Similarly one can prove the remaining cases.
COROLLARY 4. The following assertions (1)–(2) hold.
(1) If (X) = C(D2n; X), where X = D2nnZ(D2n) and gcd(n; r 1) = d, then w( (D2n)) = ( (D2n)) =n d:
(2) The commuting graph (D2n)has a perfect matching.
THEOREM 3. Ifgcd(n; r 1) =d, then ( u(D2n)) = nd + 1.
PROOF. Since gcd(n; r 1) = d, therefore j Z(D2n) j= d and the set T = f1; b; b2; : : : ; bnd 1; a; ba; b2a; : : : ; bnd 1agis a transversal ofZ(D2n)inD2n, so we have the set U =T 1 =fb; b2; : : : ; bnd 1; a; ba; b2a; : : : ; bnd 1ag. For anyj, 1 j nd 1, the setAj =fbj; a; ba; : : : ; bnd 1agis an independent set of u(D2n)and each two ele- ments of the setX =fbi;1 i nd 1g are adjacent. Thus for anyj,1 j nd 1, jAjj= nd + 1. Hence ( u(G)) = nd + 1.
COROLLARY 5. As ( (D2n)) = ( u(D2n)). Hence ( (D2n)) = nd + 1.
LEMMA 9. Ifgcd(n; r 1) =d;then ( u(D2n)) = nd 2.
COROLLARY 6. The following assertions (1)–(5) hold.
(1) If( (D2n))is the commuting graph on D2n, then ( (D2n)) = nd + (n 1)d (n+ 1).
(2) The element ais always an involution andbi ofD2n is involution ifi= n2: (3) The elements b2ia,0 i n2 1ofD2n are involutions ifr= 2k 1.
(4) The element bn2aofD2n is involution if8jnandr= 2k+ 1.
(5) The elements bni4a,1 i 4 ofD2n are involutions if8-nandr= 2k+ 1.
COROLLARY 7. The following assertions (1)–(3) hold.
(1) IfY1is the set of all involutions ofD2n forr= 2k 1, then (Y1) =F(n2 + 1;n4) is a fan graph on n2 + 1vertices and n4 number of triangles.
(2) IfY2is the set of all involutions ofD2n forr= 2k+ 1and8jn, then (Y2) =K3. (3) IfY3 is the set of all involutions of D2n forr= 2k+ 1and 8 -n, then (Y3) =
F(5;2).
COROLLARY 8. The following assertions (1)–(5) hold.
(1) In (Y1); deg(bn2) =n2 anddeg(b2ia) = 2.
(2) In (Y2); deg(bn2) = deg(bn2a) = deg(bna) = 2.
(3) In (Y3); deg(bn2) = 4anddeg(bni4 ) = 2for1 i 4.
(4) w( (Yj)) = 3 = ( (Yj))forj = 1;2;3.
(5) diam( (Y1)) = 2 =diam( (Y3))and diam( (Y2)) = 1.
Acknowledgment. We would like to thank anonymous referees for their valuable comments and suggestions.
References
[1] M. Aschbacher, A condition for the existence of a strongly embedded subgroup, Proc. Amer. Math. Soc., 38(1973), 509–511.
[2] A. Abdollahi, S. Akbary and H. R. Maimani, Non-commuting graph of a group, J. Algebra, 28(2006), 468–492.
[3] S. Akbari, H. Bidkhori and A. Mohammadian, Commuting graphs of matrix alge- bras, Comm. Algebra, 36(2008), 4020–4031.
[4] S. Akbari, M. Ghandehari, M. Hadian and A. Mohammadian, On commuting graphs of semisimple rings, Linear Algebra Appl., 390(2004), 345–355.
[5] S. Akbari, A. Mohammadian, H. Radjavi and P. Raja, On the diameters of com- muting graphs, Linear Algebra Appl., 418(2006), 161–176.
[6] D. F. Anderson and P. Livingston, The zero divisor graph of a commutative ring, J. Algebra, 217(1999), 434–447.
[7] C. Bates, D. Bundy, S. Perkins and P. Rowley, Commuting involution graphs for symmetric groups, J. Algebra, 266(2003), 133–153.
[8] C. Bates, D. Bundy, S. Perkins and P. Rowley, Commuting involution graphs for
…nite Coxeter groups, J. Group Theory, 6(2003), 461–476.
[9] C. Bates, D. Bundy, S. Perkins and P. Rowley, Commuting involution graphs in special linear groups, Comm. Algebra, 32(2004), 4179–4196.
[10] C. Bates, D. Bundy, S. Hart and P. Rowley, Commuting involution graphs for sporadic simple groups, J. Algebra, 316(2007), 849–868.
[11] T. T. Chelvam, L. Selvakumar and S. Raja, Commuting graphs on dihedral group, TJMCS, 2(2011), 402–406.
[12] A. Everett and P. Rowley, Commuting involution graphs for 4-dimensional pro- jective symplectic groups, http://eprints.ma.man.ac.uk/1564/; (preprint).
[13] B. Fischer, Finite groups generated by 3-transpositions, University of Warwick Lecture Notes, 1969.
[14] A. Iranmanesh and A. Jafarzadeh, On the commuting graph associated with the symmetric and alternating groups, J. Alg. Appl., 7(2008), 129–146.
[15] Z. Raza and S. Faizi, Non-commuting graph of …nitely presented group, Sci.
Int.(Lahore), 25(2013), 883–885.
[16] Y. Segev, The commuting graph of minimal nonsolvable groups, Geometriae Ded- icata, 88(2001), 55–66.
[17] Y. Segev and G. Seitz, Anisotropic groups of typeAn and the commuting graph of …nite simple groups, Paci…c J. Math., 202(2002), 125–225.
