Printer Friendly


Byline: Z. Raza and S. Faizi

ABSTRACT. For a non-abelian group , the non-commuting graph of is defined as the graph with vertex set and two distinct vertices and are joined by an edge whenever . In this paper, we obtain independent number, vertex chromatic number, clique number and minimum size of vertex cover of non-commuting graph, for a finitely presented group , = , where with or for any positive integer

Key Words: Non-commuting graph, clique number, chromatic number, independent number MSC: 05C12


There are many papers on assigning a graph to a ring or a group and investigation of algebraic properties of ring or group using the associated graph, for instance, see [1, 2, 3, 4, 5, 6, 7, 13, 14]. In the present article to any non-abelian group G we assign a graph and investigate algebraic properties of the group using the graph theoretical concepts. Let G be a group. One can associate a graph to G in many different ways (see, for example [8, 11, 12, 13, 14, 15]). Here we consider the following way: Let be the center of G, take as the vertices of G and join two distinct vertices and whenever . It is denoted by . Note that if G is abelian, then is the null graph. The non-commuting graph of a group G was first considered by Paul Erdos, when he posed the following problem in 1975: Let G be a group whose non-commuting graph has no infinite complete sub graph.

Is it true that there is a finite bound on the cardinalities of complete sub graphs of G? Neuman [11] answered positively Erdos's question. The group and graph-theoretic notation and terminology are standard; see [10] for group and [9] for graphs. In [2] it was conjectured that if G and H are two non-abelian finite groups such that corresponding non-commuting graphs are isomorphic, then | That is why such graph theoretical properties of non commuting graph of a group G are very much important.

In this paper, we gave an example such that the converse of the above conjecture is not true. We constructed a finite group and well know group dihedral group such that the corresponding non-commuting graphs are non isomorphic but the group have the same order.

The rest of the paper is organized as follows: Section 2 recalls some basic definitions and notations for general properties of the ordinary simple graphs. In section 3, we present our main results about the non-commuting graph of the group . In particular, we obtain the chromatic number, independent number and clique number of the non- commuting graph. We finally end up with a conclusion.


We consider simple graphs which are undirected. A subset of the vertices of is called a clique if the induced sub graph of is a complete graph. The maximum size of a clique in a graph is called the clique number of and denoted by A subset of the vertices of is called an independent set if the induced sub graph on has 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 set that contains at least one endpoint of every edge. The minimum size of a vertex cover is denoted by Let be an integer. A -vertex coloring of a graph is an assignment of colors to the vertices of such that no two adjacent vertices have the same color. The chromatic number of a graph is the minimum for which has a -vertex coloring.

If and are vertices of a graph , then denotes the length of the shortest path between and . The largest distance between all pairs of the vertices of is called the diameter of , and is denoted by


Throughout this section, we will denote and are two subsets of . It was proved in [13] that and be a transversal of in . We denote the non-commuting graph of by . Let and the induced sub graph of the elements of is denoted by . We denote and two subsets of . Any two vertices in are adjacent if and only if they are non- commutative. We also denote degree of vertex in and respectively by and . In this section we obtain certain properties of the non-commuting graph constructed on the group .

Lemma 3.1. If gcd , then = for all . Proof: Let ( denote the set of all vertices in which do not commute with . Since the centralizer of in the group is given as = Hence Also and, | Thus we have = . Lemma 3.2. If is a vertex of the non-commuting graph and gcd , then = . for all Proof: We know that there are central elements of the the group . So, in the graph , every is adjacent to all vertices in and respectively, thus we have ) Similarly, in the graph , every is adjacent to all in and in . Hence which follows the result. Theorem 3.3. If gcd , then .

Proof: Since gcd , so we have a complete commuting graph of type in Thus the number of edges of the non-commuting graph in is . But each element in does not commute with elements of so each elements of are adjacent to elements in . Thus the total number of edges of the elements of is Hence, Now the elements of form a complete graph of type So total edges of the vertices of are and each element of is adjacent to all elements of . Since number of elements in are So total edges from elements of to elements of are . Hence we have .

Theorem 3.4. .

Proof: Since all in are adjacent to all in . So . Also each commute with in whenever . So they are non-adjacent in . Thus the path whenever is of length 2, which follows the assertion of the theorem that is . Now in the graph , all are non-adjacent to each other and the path is of length 2. Hence . Corollary 3.5. From above discussion one can easily prove that . Proposition 3.6. If gcd , then Proof: We know that and the set is independent set of . If is an independent set of then Thus we have Similarly, the set is independent set of and clearly we have . Hence we get Theorem 3.7. If gcd , then Proof: We now that, if gcd then and be a transversal of in . Also for every , The vertex is adjacent with vertex . Thus the set , is a clique of . On the other hand each two elements of are non-adjacent. Hence is a clique of and . Hence One can observed that is also the clique of . Thus, we have Corollary 3.8. If then if and only if Corollary 3.9. If then is - regular if and only if Lemma 3.10.

There exist no subset of such that . Proof: Suppose for some subset of . Then must contain one element from and three elements from . Since these three elements from form a complete graph, a contradiction, hence follows the result. As prove above one can prove the following: Corollary 3.11. There does not exist any subset of such that and . Proposition 3.12. Proof: Since is independent set of vertices in , so we assign same color to all of the vertices in . The induced subgraph of is complete. So we assign colors to all of the vertices in which shows Also the induced subgraph of is complete and . Hence . Similarly it can be easily proved that which complete the proof.

Theorem 3.13. Proof: Since the induced subgraph of is complete in Also the subset of is a vertex cover of such that . Hence . Similarly the induced subgraph of is also complete in which shows and the subset of is a vertex cover of such that . Hence we have Corollary 3.14. The induced graph always represents a split graph. Proof: The proof follows from Theorem 3.10 and Proposition 3.12.


In this research work, we studies some graph properties of the non-commuting graph of the group . In particular, we give several results about the non- commuting graph of the group such as chromatic number, clique number and independent number. In future, we will try to study the similar graph properties of the non-commuting graph for the Coexter group and other finitely presented non- abelain groups.


1. A. Asghar Talebi, Non-commuting graphs on dihedral group, Int. J. Algebra, 2(20): 957- 961(2008).

2. A. Abdollahi, S. Akbary and H. R. Maimani, Non- commuting graph of a group, J. Algebra, 28: 468- 492(2006).

3. S. Akbari and A. Mohammadian, On the zero-divisor graph of a commutative ring, J. Algebra, 274(2): 847- 855(2004).

4. S. Akbari, H. R. Maimani and S. Yassemi, When a zero-divisor graph is planar or complete r-partite graph, J. Algebra, 270: 169-180(2003).

5. D. F. Anderson and P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217: 434- 447(1999).

6. I. Beck, Coloring of commutative rings, J. Algebra, 116: 208-226: (1988).

7. E. A. Bertram, Some applications of graph theory to finite groups, Discrete Math., 44: 31-43(1983).

8. E. A. Bertram, M. Herzog and A. Mann, On the graph related to conjugacy classes of groups, Bull. London Math. Soc., 22 (6): 569-575(1990).

9. J. A. Bondy, and J. S. Murty, Graph theory with application, Elsevier, (1977).

10. D. S. Dummit and R. M. Foote, Abstract Algebra, John Wiley and Son, Singapore, (2005).

11. B. H. Neumann, A problem of Paul Erdos on groups, J. Aust. Math. Soc. Ser. A, 21: 467-472(1976).

12. L. Pyber, The number of pairwise non-commuting elements and the index of the centre in a finite group, J. London Math. Soc., 35 (2) 287-295(1987).

13. Z. Raza and S. Faizi, Commuting graphs of dihedral type groups to appear.

14. Y. Segev, The commuting graph of minimal non- solvable groups, Geom. Dedicata, 88 (1-3) 55- 66(2001).

15. J. S. Williams, Prime graph components of finite groups, J. Algebra, 69 (2), 487-513 (1981).

Department of Mathematics, National University of Computer and Emerging Sciences, Lahore Campus, Pakistan, Department of Mathematics, Virtual University, Lahore, Pakistan,
COPYRIGHT 2013 Asianet-Pakistan
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Raza, Z.; Faizi, S.
Publication:Science International
Article Type:Report
Date:Dec 31, 2013

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters