Microsoft Word - 149-155   149  Ibn Al-Haitham Jour. for Pure & Appl. Sci. 33 (2) 2020       Chromatic Number of Pseudo-Von neuman Regular Graph Nabeel E. Arif Nermen J. Khalel Article history: Received 18 June 2019, Accepted 17 July 2019, Published in April 2020. Abstract Let R be a commutative ring , the pseudo – von neuman regular graph of the ring R is define as a graph whose vertex set consists of all elements of R and any two distinct vertices a and b are adjacent if and only if 𝑎 𝑎 𝑏 or 𝑏 𝑏 𝑎 , this graph denoted by P-VG(R) , in this work we got some new results a bout chromatic number of P-VG(R). Keywords: Graph, Chromatic Number, Commutative Ring. 1. Introduction Beck [1]. Studied coloring of commutative rings and studied chromatic number of it is graph such that two different elements x and y are adjacent iff xy = 0, Bhavanari S. et.al. studied prime graph of a ring with some properties of its graph [2]. Kalita S. [3]. Computed chromatic number of prime graph of some finite ring, patra k. et.al [4]. Studied chromatic number of prime graph of some rings namely 𝑍 , where n=∏ 𝑝 , Elizabeth R. [5]. Studied colorings of zero divisor graphs of commutative rings , in this paper we define pseudo-von neman regular graph of the ring R with some result of it graph and we study chromatic number of pseudo-von neman regular graph. 2. Primer lay Definition 1: [6]. A nonempty set R, together with two binary operations (+ ) and ( ∙ ) is said to be a ring if the following are satisfied i- (R,+) is an a belian group ii- (R,∙ ) is a semi-group iii- s∙(t+l) = s∙t + s∙l and (s+t) ∙l = s∙l+t∙l for any s, t, l ∈R Definition 2: [7]. let R be a ring and a ∈R , a is called regular element if there exist b∈R such that a=aba , if any element in R is regular then R is regular ring , if R is commutative then 𝑎 𝑎 𝑏 and we say that R is Von Neumann regular ring. Ibn Al Haitham Journal for Pure and Applied Science Journal homepage: http://jih.uobaghdad.edu.iq/index.php/j/index Doi: 10.30526/33.2.2436                  nabarif@tu.edu.iq nrnjamal88@gmail.com Department of Mathematic, College of Computer Science and Mathematics, Tikrit University, Tikrit, Iraq.   150  Ibn Al-Haitham Jour. for Pure & Appl. Sci. 33 (2) 2020 Definition 3: [8]. A graph G is defined by an ordered pair (V (G) , E (G) ), when V(G) is a non empty set whose elements are called vertices and E(G) is a set ( may be empty ) of unordered pairs of distinct vertices of V(G) . the element of E(G) are called edges of the graph G . we denote by 𝑢𝑣 , an edge between two end vertices u and v . Definition 4: [8]. An edge whose end-vertices are the same is called loop. Definition 5: [8]. If there are more than one edges associated with a given pair of vertices , then these edges are called multiple edges or parallel edges. Definition 6: [8]. A simple graph that has no self-loops or multiple edges . Definition 7: [8]. A graph H is said to be a subgraph of a graph G if all the edges and all the vertices of H are in G , and each edge of H has the same end vertices in H as in G . Definition 8: [9]. A path is a graph G that contains a list𝑣 , 𝑣 , … , 𝑣 of vertices of G s.t. for 1 𝑖 𝑝 1 , there is an edge 𝑣 , 𝑣 in G and these are the only edges in G . Definition 9: [9]. let 𝑣 and 𝑣 be two vertices , d (𝑣 , 𝑣 ) is called a distance from 𝑣 to 𝑣 if it is the shortest path from 𝑣 to 𝑣 . Definition 10: [9]. A close path is called cylce , the degree of each vertex of a cycle graph is two , a cycle with n vertices denoted by 𝐶 . Definition 11: [10]. Let G( V, E ) be a graph and C ⊂ G , is called clique if the induced sub graph of G induced by C is a complete graph . The clique is called maximal if there is no clique with more vertices . Definition 12: [11]. A h-coloring of the vertex set of a graph G is a function 𝛾: V(G) → 1,2, … , ℎ such that 𝛾(𝑣 ) 𝛾(𝑣 ) whenever 𝑣 is adjacent to 𝑣 , if a h- coloring of G exists, then G is called h- colorable. Definition 13: [11]. The chromatic number of G is defined as 𝒳 (𝐺) = min { h : G is h- colorable } Where 𝒳 (𝐺) = h , G is called h- chromatic. Theorem 14 [10]. for circular graph 𝐶 one has 𝒳 (𝐶 )= 2 𝑤ℎ𝑒𝑛 𝑛 𝑖𝑠 𝑒𝑣𝑒𝑛 3 𝑤ℎ𝑒𝑛 𝑛 𝑖𝑠 𝑜𝑑𝑑 In other words 𝒳 (𝐶 ) = 3 , 𝒳 (𝐶 )= 2 for i ∈ {1,2, 3, …}. Theorem 15: [3]. Let R be a ring , B(R) ={(a, b) : aRb = 0 or bRa = 0, a, b ∈R, a b, a 0, b 0}. Then χ PG(R)= χ G(B(R)) +1, when G(B(R)) is the induced sub graph of PG(R) whose edges are elements of B(R). 3. Main Result Definition 3.1: let R be a commutative ring. A graph G (V , E ) is said to be (pseudo-von neumann regular graph ) of R if V(G) =R and E (G) ={ 𝑎𝑏/ 𝑎 𝑎 𝑏 or 𝑏 𝑏 𝑎 and 𝑎 𝑏 } denoted by P-VG(R) , shortly p-von Neumann regular graph .   151  Ibn Al-Haitham Jour. for Pure & Appl. Sci. 33 (2) 2020 Example 3.2 𝑍 ={0,1} Figure 1: P-VG(𝑍 ) 𝑍 ={0,1,2} Figure 2:P-VG(𝑍 ) 𝑍 ={0,1,2,3} Figure 3:P-VG(𝑍 ) 𝑍 ={0,1,2,3,4} Figure 4:P-VG(𝑍 ) Note 3.3 C [R] = { 𝑎, 𝑏 ∶ 𝑎 𝑏 , 𝑎 0 𝑎𝑛𝑑 𝑏 0, 𝑎 𝑎 𝑏 or 𝑏 𝑏 𝑎} ⊂ R R. Corollary 3.4 i- The number of element in C [R] is less than or equal to number of cycle 𝐶 in P-VG(R). ii- If C [R] ∅ , then the longest trail has length 3. iii- C [R] R R. Proof i- Let (a,b) ∈ C [R], then { 0, a, b } form a cycle 𝐶 in P-VG(R) , if (a,b) , (s,t) ∈ C [R] such that (a,b) (s,t) then a s or b t and so the cycle 𝐶 { 0, a, b } and { 0, s, t } in P-VG(R) are distinct , this show the number of elements in C [R] is less than or equal the number of cycle 𝐶 in P-VG(R). if a=s or b=t then the cycles { 0, a, b } , { 0, s, t} are adjust. 0 1 0 1 2 0 1 2 3 0 1 2 3 4   152  Ibn Al-Haitham Jour. for Pure & Appl. Sci. 33 (2) 2020 ii- Let (a,b) ∈ C [R],then 0a , ab , 0b is cycle 𝐶 , this trail is of length equal to 3 hence , the longest trail has length 3. iii- Since (0,a) ∈ 𝑅 𝑅 and (0,a) ∉ C [R] , then we have C [R] ⊂ 𝑅 𝑅 and C [R] 𝑅 𝑅 . By the same way of (theorem 2.15) we can prove below theorem. Theorem 3.5 Let R be a ring and let C [R] = { 𝑎, 𝑏 ∶ 𝑎 𝑏 , 𝑎 0 𝑎𝑛𝑑 𝑏 0, 𝑎 𝑎 𝑏 or 𝑏 𝑏 𝑎} then 𝒳 ( P-VG(R) )= 𝒳 ( G(C [R] ) + 1 , where G(C [R]) is sub graph of P-VG(R) . Proof Let R be a ring , let C [R] = { 𝑎, 𝑏 ∶ 𝑎 𝑏 , 𝑎 0 𝑎𝑛𝑑 𝑏 0, 𝑎 𝑎 𝑏 or 𝑏 𝑏 𝑎} If C [R] = ∅ , then P-VG(R) graph is a star graph and 𝒳( P-VG(R) ) =2 Suppose C [R] ∅ , let |𝐶 𝑅 |= n Case i: let G(C [R]) = 𝑃 then 𝒳 ( G(C [R] ) is equal to 2 , since 0 is adjacent to all vertices in P- VG(R), so we have a third color to a vertex 0 , Now the vertices do not belong to 𝑃 will be associated only with vertex 0, this vertices can colored by any color we used it in 𝑃 . hence 𝒳 ( P-VG(R) ) = 3 = 𝒳 ( G(C [R] ) +1 Case ii: Now if G(C [R]) = 𝐶 then 𝒳 ( G(C [R]) ) must equal to 2 when n is even and equal to 3 when n is odd , and the vertex 0 adjacent to all vertices , implies that 𝒳 ( P-VG(R) ) equal to 3 if n is even and equal to 4 if n is odd, hence 𝒳 ( P-VG(R) ) = 𝒳 ( G(C [R] ) +1. Case iii : Let G(C [R] is an i-partite graph where G(C [R]) = 𝐾 , ,…, , then 𝒳 ( G(C [R]) ) = i , then we have 𝒳 ( P-VG(R) ) = i+1 = 𝒳 ( G(C [R] ) +1 Case iv: If G(C [R]) = 𝐾 then the chromatic number of G(C [R]) ) equal to h and therefore 𝒳 ( P-VG(R) )= h+1 = 𝒳 ( G(C [R] ) +1 Case v: Now if G(C [R]) is a connected graph and it includes a maximal clique 𝐾 , 𝑖 2 then the chromatic number of 𝐾 equal to i , and the rest of the vertices of G(C [R]) can be colored by any colors of the vertices of 𝐾 because they are not associated with it . then 𝒳 ( G(C [R]) ) = i and 𝒳 ( P-VG(R) )= i+1 = 𝒳 ( G(C [R] ) +1 Case vi : Let 𝐺 , 𝐺 , … , 𝐺 be a disjoint components of G(C [R]) then 𝒳 ( G(C [R]) ) = max { 𝒳𝐺 , 𝒳𝐺 , … , 𝒳𝐺 } , suppose 𝒳 ( G(C [R]) )= s Now if we have a vertices of P-VG(R) with degree 1 this can be colored by any color of these s colors used to color G(C [R]) , and the vertex 0 has another color since it adjacent to all vertices , this implies that 𝒳 ( P-VG(R) )= s+1= 𝒳 ( G(C [R] ) +1 . From all above cases then 𝒳 ( P-VG(R) )= 𝒳 ( G(C [R] ) +1 Lemma 3.6 Let R=𝑍 be a ring , where p 3 is prime number then 𝒳 ( P-VG(R) ) =3.   153  Ibn Al-Haitham Jour. for Pure & Appl. Sci. 33 (2) 2020 Proof Let 𝑎𝑏 ∈ VG (R) then 𝑎 𝑎 𝑏 or 𝑏 𝑎 , 𝑎 𝑏 and 𝑎 0 𝑏, since p is prime then R is afield implies that 𝑏 𝑎 or 𝑎 𝑏 is unique number satisfy the equation , since 𝑎0 , 𝑏0 ∈ E(P-VG(R)) then P-VG(R) graph has cycle 𝐶 , then by( throrem 2.14 ) 𝒳 ( P-VG(R) )=3 Example 3.7 The chromatic number of P –Von Neumann regular graph of 𝑍 , 𝑍 and 𝑍 are 4 Figure 5:P-VG(Z ) Figure 6: P-VG(𝑍 ) Theorem 3.8 The ring 𝑍 , 𝒳 ( P-VG(𝑍 ))=3 where p 3 is prime number. Example 3.9 R= 𝑍 then 𝒳 ( P-VG(𝑍 )) = 3 . 6 9 4 7 8 2 3 5 1 0 4 12 2 11 9 613 7 1 8 3 5 10 0   154  Ibn Al-Haitham Jour. for Pure & Appl. Sci. 33 (2) 2020 Figure 7: P-VG(𝑍 ) Note 3.10 If R= 𝑍 and 𝑎𝑏 ∈ E ( P-VG(𝑍 )) then 𝑎 𝑎 𝑏 and 𝑏 𝑏 𝑎 and ab mod p =1. Theorem 3.11 The ring 𝑍 , 𝒳 ( P-VG(𝑍 ))=3, when p 3 is a prime number and n a positive integer . Proof let a ,b ∈ 𝑍 and a b , a 0 b and 𝑎𝑏 ∈ E(P-VG(𝑍 )) Then 𝑎 𝑎 𝑏 and 𝑏 𝑏 𝑎 and ab=1 and since b is unique (because b is the inverse of a , and it is only element satisfy the equation ) Then P-VG(𝑍 ) has only cycle 𝐶 by theorem ( 2.14 ) every cycle has odd vertices has chromatic number equal to 3 and in any P-VG(𝑍 ) graph has more than one 𝐶 , and all 𝐶 in a graph commend in one vertex (0) , so the vertex has one color it is clear that the color of other vertices in the same cycle are two another colors , so we have only three colors in any P-VG(𝑍 ) . 4. Conclusion In this work we gave a definition of pseudo-von Neumann regular graph P-VG(R) then proved the chromatic number 𝒳 ( P-VG(R) )= 𝒳 ( G(C [R] ) + 1 when 𝑎 𝑏 0 and 𝒳 ( P-VG(𝑍 ) ) , 𝑝 3 is equal to 3 , and 𝒳 (P-VG(𝑍 )) , 𝑝 3 equal to 3. 2 20 15 12 2311 9 22 8 21 5 17 0 14 24 18 7 6 19 4 3 13 10 16 1 0   155  Ibn Al-Haitham Jour. for Pure & Appl. Sci. 33 (2) 2020 References 1. Beck, I. Coloring of commutative rings, J. Algebra.1988, 116, 1, 208-226. 2. Gross, J.L.; Yellen, J. Graph theory and its Applications, second edition, Chapman & Francis Group, Boca Raton.2006, FL33487-2742. 3. Patra, K.; Kalita, S. Prime Graph of the Commutative Rings 𝑍 . UTM center for Industrial and Applied Mathematics.2014, 30, 1, 59-67. 4. Rahman, Md.S. Basic Graph Theoey, first edition, Springer, 2017. 5. Ramos, R.E. colorings of zero-Divisor Graphs of commutative rings, M.Sc.Thesis, North Dakota state University, 2015. 6. Lewis, R.M.R. A Guide to Graph Colouring Algorthms and Applications, first edition, Springer.2016, ISBN 978-3-319-25730-3. 7. Kalita, S. Some Aspects of Prime Graph of Some Rings, Ph.D. Thesis, University of Gauhati, India, 2014. 8. Bhavanari, S.; Kuncham, S.; Dasari, N. Prime Graph of a Ring. Journal of Combinatorics, Information and System Sciences.2010, 35, 1-2, 27-42.\ 9. Bhavanari, S.; Kuncham, S.P. Discrete Mathematics and Graph Theory, first edition, PHL Learning Private Limited, Delhi, 2014. 10. AL-Hisso, Sh. Types of strongly Regular Rings, M.Sc. Thesis, Mosul University, 2004. 11. Khanna, V.K.; Bhambri, S.K. A Course in Abstract Algebra, first edition, vikas publishing house PVT LTP, 2004.