Prime Labelling with Spiral Gaussian integersS.Kavitha1 and G.Jayalalitha21S.Kavitha,Research scholar, Bharathiar University,Coimbatore,Tamilnadu,India [email protected],Associate Professor,Department of Mathematics,Vels University,Chennai,Tamilnadu,[email protected] A Prime Labelling of a graph G with n vertices is a assignment of first n natural numbers to the vertices of G such that any two adjacent vertices have relatively prime we extended the idea to the Gaussian integers. In this paper define an order on the Gaussian integers that lie in the two-dimensional XY plane using this ordering we make a spiral structure and show that several families of trees and Knight graph which admit a prime labelling with the Gaussian integers.Key words: Prime labelling, Spiral order, Gaussian integers, Star Graph, Knight Graph1. Introduction A labelling graph G with n vertices is called a prime labelling if its vertices can be labelled with the n natural numbers such that any two adjacent vertices have relatively prime. Many families of graphs are unknown to admit prime labelling. Such as paths, stars, caterpillars, complete binary trees, spiders, palm trees, fans, flowers and many more 1,2. In this paper, extended the study of prime labelling to the Gaussian integers, which are the complex numbers whose real and imaginary parts are both integers. In this paper, deal with the prime labelling to Gaussian integers for the spiral ordering we must first define what we mean by the first n Gaussian integers. In section 2, definition of Gaussian integers and prime Gaussian integers are discussed and define a two-dimensional XY plane spiral ordering on the Gaussian integers that allows us to linearly order the Gaussian integers. This XY plane spiral ordering preserves many familiar properties of the natural ordering on N and discuss further properties of the spiral ordering. In section 3, we apply the Spiral ordering to prove that several families of trees admit a prime labelling with the Gaussian integers under the spiral ordering. Here also discuss the other graph which admits the prime labelling with the Gaussian integers.2. a. Back ground and definitions5 We start with some pertinent background on Gaussian integers to furnish a foundation for our work. The Gaussian integers, denoted Zi are the complex numbers of the form a+bi, where a,b? Z and i^2=-1. A unit in the Gaussian integers is one of +1, + i. An associate of Gaussian integers ? is u.? where u is a Gaussian unit. The norm of a Gaussian integer a+bi, denoted by N(a+bi), is given by a^2+b^2. A Gaussian integer is even if it is divisible by 1+i and odd otherwise. This is because Gaussian integers with even norms are divisibly by 1+i.Definition2.1.A Gaussian integer ? is prime if its only divisors are ±1,±i,±?,±?i. Besides this definition of Gaussian primes, we have the following characterization theorem for Gaussian primes. Further information on the Gaussian integers can be found in Rosen’s elementary Number Theory 3.Theorem 2.2.A Gaussian integer ? ? Zi is prime if and only if either ?= ±(1+i) N(?) is a prime intger congruent to 1 (mod 4), or ?=p+0i or ?=0+pi where p is a prime in Z and |p|?3(mod 4)Definition 2.3 Let ? and ? be Gaussian integers. We say ? and ? are relatively prime or co prime if their only common divisors are the units in Zi2.b. Prime Labelling of graphs with Gaussian integers Here we consider the finite graphs without loops or multiple edges, and particularly we will study about trees and other graphs. In a tree, a vertex is called a leaf or end vertex if it has degree one and otherwise a vertex is called Internal nodes. 5 Our goal is to extend the study of the prime labelling with Gaussian integers. Because the Gaussian integers are not totally ordered, we must first give an appropriate definition of “the first n Gaussian integers”. We propose the following ordering.Definition 2.4 The spiral ordering of the Gaussian integers is recursively defined ordering of the Gaussian integers. We denote the nth Gaussian integers in the spiral ordering by ?n. The ordering is defined beginning with ?n=1 and continuing as:?_(n+1)={?(((?_n+i, Im(?_n )?1(mod2) Re(?_n )>0)¦(?_n+i, Im(?_n )?0(mod2) Re(?_n )>0))¦((?_n+1, Re(?_n )?1(mod2) Im(?_n )?0)¦( ?_n+1, Re(?_n )?0(mod2) Im(?_n )?0))@((?_n-i, Im(?_n )?1(mod2) Re(?_n )<0)¦(?_n-i, Im(?_n )?0(mod2) Re(?_n )<0))¦((?_n-1, Re(?_n )?1(mod2) Im(?_n )?0)¦(?_n-1, Re(?_n )?0(mod2) Im(?_n )?0)))?This is illustrated in Fig.1. Under this ordering, the first 10 Gaussian integers are1,1+i,i,-1+i,-1,-1-i,-i,1-i,2-i,2and we write ?_n to denote the set of the first n Gaussian integers in the spiral ordering. Consecutive Gaussian integer in this ordering are separated by a unit and therefore alternate parity, as in the usual ordering of N. However, several properties of the ordering integers do not hold. In the set of first N(1+2i).knumbers (k?N), it is not guaranteed that there are exactly k multiples of 1+2i (or any other residual class mod 1+2i). Furthermore, odd integers with indices separated by a power of two are not guaranteed to be relatively prime to each other. This definition of the spiral ordering for the Gaussian integers leads to the following definition of prime labelling of prime labelling of trees and other graphs Gaussian integers. Fig.1.Spiral ordering of the Gaussian IntegersDefinition2.5.Let G be a graph with n vertices. A Gaussian prime labelling of G is a bisection fromf:V(G)??_n such that if uv?E(G), then f(u) and f(v) are relatively prime, that is, neighbouring vertices have relatively prime labels.2.c. Properties of the spiral ordering Several pieces of Gaussian spiral ordering are defined here. When the spiral turns from east to north or north to west or west to south or south to east corners of the spiral ordering occur. Branches of the spiral occur when the spiral travels along a straight path going north, south, east or west. Our first goal is to determine the index of an arbitrary Gaussian integer, a+bi in the spiral order based on which type of branch or corners it lies on. We use I(a+bi) to denote the index of a+bi in the spiral ordering. These are four types of corners: Gaussian integers in the I quadrant,Re(z)-Im(z)=0 andRe(z)>0 ,Im(z)>0 Gaussian integers in the II quadrant,Re(z)+Im(z)=0 andRe(z)<0 ,Im(z)>0 Gaussian integers in the III quadrant,Re(z)+Im(z)=0 andRe(z)<0 ,Im(z)>0 Gaussian integers in the IV quadrant,Re(z)+Im(z)=0 andRe(z)>0 ,Im(z)<0Similarly, the branches come in four types. Up-oriented branches, which contain Gaussian integers between IV quadrant corners to I quadrant corners. Left-oriented branches, which contain Gaussian integers between I quadrant corners to II quadrant corners. Down-oriented branches, which contain Gaussian integers between II quadrant corners to III quadrant corners. Right-oriented branches, which contain Gaussian integers between III quadrant corners to IV quadrant corners.Lemma 2.6 Indices of four types of corners are found as follows:I(a+bi)={?(4a^2-2a,ifcorners lie in I and [email protected]?(a-b)?^2,ifcorners lie in II and IVquadrants)?Theorem 2.7 Let a+bi be a Gaussian integer. Then its index in the spiral ordering I(a+bi) for the branches are given by the following formula:I(a+bi)={?((4a^2-3a+b, up-oriented branches)¦(4b^2-(a+b), left-oriented branches)@(4a^2-(a+b) ,down-oriented branches)¦(4b^2-3b+a,right-oriented branches))? Lemma 2.8 Let ? be a Gaussian integer and u be a unit. Then ? and ?+u is relatively prime.Corollary 2.9. Consecutive Gaussian integers in the spiral ordering are relatively prime.Lemma 2.10.Let ? be an odd Gaussian integer. Let c be a positive integer, and let u be a unit. Then ? and ?+u.?(1+i)?^c are relatively prime.Corollory 2.11.Consecutive odd Gaussian integers in the spiral ordering are relatively prime.Lemma 2.12. Let ? be a Gaussian integer and let ? be a prime Gaussian integer. Then ? and ?+? are relatively prime if and only if ???.Lemma 2.13. Let p?N be a prime integer congruent to 3(mod 4) and let ? = a+bi be a Gaussian integer such that p | ?. Then the index of ? in the spiral ordering is congruent to 0 or 2(mod p)3.Results for families of trees and other graphs:Definition 3.1.The star graph,S_n, on n vertices is the graph with V(S_n)={V_1,V_2,V_3,…..V_n}and E(S_n)={ V_1 V_k:2?k?n}(Fig.2)Theorem 3.2.Any star graph admits a Gaussian prime labellingDefinition 3.3.The path graph, P_n, on n vertices is the graph with V(P_n)={V_1,V_2,V_3,…..V_n} and E(P_n)={ V_j V_(j+1):1?j?n-1} (Fig.3) Fig.2. The star graph on 9 verticesTheorem 3.4. Any path admits a Gaussian prime labelling. Fig.3.The path graphDefinition3.5. Let n,k,m be integers with k?m. The (n,k,m)-double star tree,DS_(n,k,m),is the graph with V(DS_(n,k,m) )={v_1,…..,v_n,v_(n+1),….,v_(n+k-1),v_(n+k),….,v_(n+k+m-2) },andE(DS_(n,k,m) )={v_j v_(j+1):1?j?n-1,v_1 v_(n+j):1?j?k-1,v_n v_(n+k+j):0?j?m-2}In the (n,k,m)-double star tree we have a path of length n whose end vertices v_1and v_nare the central vertices for stars on k and m vertices respectively(not including the other vertices on path) (Fig.4)Theorem3.6.Any (n,k,m)-double star tree has a Gaussian prime labelling.Proof: Label v_1with ?_1=1, v_n with ?_2=1+i. Let S_2 be the set of all odd vertices and S_1 be the set of all other vertices. Since 1+i is relatively prime to all odd vertices and 1 is relatively prime to all Gaussian integers, this is a Gaussian prime labelling. Fig.4. The (2,12,12)-double star treeDefinition 3.7.A Spider graph is a tree with one vertex degree at least 3 and all other vertices having degree 1 or 2 (Fig.5) Fig.5.The spider graphTheorem 3.8. Any spider tree admits a Gaussian prime labelling.Proof: Let T be a spider tree and suppose the centre vertex V_1 has degree k. We label V_1 with ?_1=1 and label the all k adjacent vertices with even Gaussian integers ie) Gaussian integers divisible by 1+i. Label the vertices which are adjacent to the k vertices with the odd Gaussian integers, then by corollary2.9 this is a Gaussian prime labelling.Definition 3.9. A knight's graph or a knight's tour graph is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other. (Fig.6)Theorem 3.10. A knight graph with 16 vertices admits a Gaussian prime labelling.Proof: Label the vertices v_i by ?_i. This is a Gaussian prime labelling because by theorem2.2, except v_12 and v_16 all other vertices are Gaussian prime integers, v_12 and v_16 are adjacent to prime Gaussian integers. Fig.5.The knight graph on 16 verticesReferences1Joseph A.Gallian, A dynamic survey of graph labelling, Electron.J. Combin.21 (2014) 43. Dynamic Survey 6 (electronic)2 Leanne Robertson, Ben small, On Newman's conjecture and prime trees,Integers 9 (A10) (2009) 117-128.3K.H.Rosen, Elementary Number theory and Its Applications, Addison-wesley,2011.4Hunter Lehmann, Andrew Park, Prime labelling of small trees with the Gaussian integers, Rose-Hulman Undergrad. Math J. (2015) Preprint available: http://fac-staff.seattleu.edu/klees/web/SmallTrees.pdf,inpress.5S. Klee, et al., Prime labelling of families of trees with Gaussian integers, AKCE International Journal of Graphs and Combinatorics (2016), http://dx.doi.org/10.1016/j.akcej.2016.04.001