Gutman u in{0, 1, …, n ? 1}

Gutman Index and Harary Index of Unitary Cayley GraphsAbstractIn this paper, we determine the Gutman Index and Harary Indexof Unitary Cayley Graphs. The Unitary Cayley Graph Xnis the graph with vertex set V (Xn) ={u|u ? Zn} and edge set{uv|gcd(u ? v, n) = 1 and u, v ? Zn}, where Zn ={0, 1, …, n ? 1}Keywords : Unitary Cayley Graphs, Gutman Index, Harary Index.2010 AMS Classification : 05C50, 05C781 IntroductionThe general concepts of graph theory can be viewed in 2. Here, weconsider the Unitary Cayley Graph Xn = Cay(Zn; Un) where Zn is theadditive group of intergers modulo n and Un is the multiplicative groupof its units (n > 1) . Therefore, its vertex set comprises of elements u in{0, 1, …, n ? 1} and u, v are adjacent if and only if gcd(u ? v, n) = 1. Xnis ?(n)-regular where ?(n) =|Un|. Also, it is complete when n is prime pand complete bipartite when n is a prime power pt (for the properties ofunitary Cayley graphs, see 4).A topological index, also known as graph-theoretic index, is graph in-variant and is a type of molecular descriptor 3. Several distance-basedand degree-based topological indices have been defined. Among them, we1Correspondence : [email protected] Roshan Sara Philipose and Sarasija P.Bchoose 2 distance based topological indices? Gutman Index and HararyIndex for the computation of the respective indices of Unitary Cayleygraphs.Gutman proposed the idea of Gutman Index Gut(G) (Schultz index of the2nd kind) of a connected undirected graph G in 1994 1and it is definedasGut(G) =Xu,v2V (G)d(u)d(v)dG(u, v).Plav?si´c introduced the Harary index 5 of a graph G on n verticesin 1993 and it is defined asH(G) =Xu,v2V (G)1dG(u, v)In both defintions, the summation goes over all unordered pairs of verticesof G, V (G) represents the vertex set of graph G and dG(u, v) denotes thenumber of edges in a shortest path connecting vertices u and v. Also, d(u)and d(v) denote the degrees of vertices u and v.In this paper, the folowing two lemmas (for the proof, see 3) are appliedfor the computation.LEMMA 1.1. The Unitary Cayley graph Xn, n ? 2, is bipartite if andonly if n is even.LEMMA 1.2. For integers n ? 2, a and b, denote by Fn(a?b) the numberof common neighbours of distinct vertices a, b in the Unitary Cayley graphXn is given byFn(a ? b) = nYp/n(1 ??(p)p), where ?(p) =(1, if p divides (a-b)2, if p doesnot divide (a-b)(1)(p is prime).2 Gutman Index of Unitary Cayley GraphsIn this section, Gutman Index of the Unitary Cayley graphs is determined.THEOREM 2.1. Let Xn be the Unitary Cayley graph on n vertices.Then for an integer n ? 2, we deduce:Gutman Index and Harary Index of Unitary Cayley Graphs 31. if n is prime, Gut(Xn) = n(n?1)32 .2. if n = 2r and r > 1, Gut(Xn) = n3(3n?4)16 .3. if n is odd but not prime, Gut(Xn) = n(n)22(n?1)?(n)2 .4. if n is even and has an odd prime divisor, Gut(Xn) = n(n)25n?4((n)+1)4 .Proof. Let Xn be the Unitary Cayley graph and Xn is ?(n)-regular.1. Suppose n is prime p.Then Xp = Kp, a complete graph.Therefore, by definition of Gut(G) and H(G),Gut(Xn) = ?(n)2 + ?(n)2 + · · · + ?(n)2| {z }n(n?1)2= (n?1)2·n(n ? 1)2 =n(n ? 1)32.2. Suppose n = 2r and r > 1.Then Xn = Kn/2,n/2, a complete bipartite graph with V (Xn) =V (AUB); A = {0, 2, …, n ? 2}, B = {1, 3, …, n ? 1}.Therefore, by applying lemma 1.2, we obtain the distance between(n/2)2 pairs of vertices as 1 and distance between n(n?2)4 pairs ofvertices as 2.So, Gut(Xn) =Xu,v2V (Xn)d(u)d(v)dG(u, v)=Xu,v2V (Xn)d(u)d(v) + 2Xu,v2V (Xn)d(u)d(v)= (n/2)2X1 + (n/2)2X2= (n/2)2 · n2/4 + 2(n/2)2 ·n(n ? 2)4=n3(3n ? 4)16.3. Suppose n is odd but not prime.i.e., n = (p1) 1(p2) 2 · · · (pr) r ; pi 6= 2 and 1 ? i ? r. Therefore,we can infer that to every pair of distinct vertices, there exists acommon neighbour by lemma 1.2.4 Roshan Sara Philipose and Sarasija P.BThen distance between n(n)2 pairs of vertices is 1 and distance be-tween nn?((n)+1)2 pairs of vertices is 2.Therefore, Gut(Xn) =Xu,v2V (Xn)d(u)d(v)dG(u, v)=X?(n)2 + 2X?(n)2= ?(n)2 · n?(n)2 + 2n?(n)2 · n ? (?(n) + 1)2=n?(n)22(n ? 1) ? ?(n)2.4. Suppose n is even and has an odd prime divisor p. Then Xn is bipar-tite with vertex partition A = {0, 2, …, n ? 2} and B = {1, 3, …, n ? 1}.Also, d(u) = d(v) = ?(n) since Xn is ?(n)-regular.Claim: Calculate dG(u, v)To obtain dG(u, v), consider 2 cases.Case 1: Consider u ? A.Taking v ? A, we obtain a common neighbour by lemma 1.2. ThusdG(u, v) = 2. Taking v ? B, we obtain dG(u, v) = 1 and dG(u, v) = 3by considering B as the union of 2 sets B1 and B2 comprising of el-ements adjacent to u and non-adjacent to v respectively.Case 2: Consider u ? B.Similarly, we obtain dG(u, v) as 1, 2 and 3 when v ? B1, v ? A andv ? B2 respectively.Thus, Gut(Xn) =Xu,v2V (Xn)d(u)d(v)dG(u, v)=Xu,v2V (Xn)d(u)d(v) + 2Xu,v2V (Xn)d(u)d(v) + 3Xu,v2V (Xn)d(u)d(v)=?(n)2 · n?(n)2+ 2?(n)2 · (n2 ? 2n)4+ 3?(n)2n/2 ? ?(n)n2=n?(n)25n ? 4(?(n) + 1)4.Gutman Index and Harary Index of Unitary Cayley Graphs 53 Harary Index of Unitary Cayley GraphsWe determine Harary Index of Unitary Cayley graphs in this section.THEOREM 3.1. For the Unitary Cayley graph Xn (n > 1),the Harary Index ,H(Xn) =?????????n(n?1)2 , n is primen(3n?2)8 , n = 2r and r > 1n((n)+n?1)4 , n is odd but not primen5n+2(4(n)?3)24 , n is even and has an odd prime divisorProof. For n is prime, we get a complete graph Xn. So by definition,H(Xn) = |1 + 1{·z· · + 1}n(n?1)2= n(n?1)2 .For n = 2r and r > 1, we get a biclique Xn with vertex partition. ThusH(Xn) = n(3n?2)8 .For n is odd but not prime, we get dG(u, v) as 1 and 2 (using lemma 1.2)respectively.Thus H(Xn) =Xu,v2V (Xn)1dG(u, v)=n?(n)2+ 1/2 ·nn ? (?(n) + 1)2=n?(n) + n ? 14.For n is even and has an odd prime divisor, we get a bigraph Xn. Thenit can be easily understood from theorem 2.1 that dG(u, v) is 1, 2 and 3respectively.Thus H(Xn) =Xu,v2V (Xn)1dG(u, v)=X11+X12+X13=n?(n)2+n2 ? 2n8+nn/2 ? ?(n)6=n5n + 2(4?(n) ? 3)24.6 Roshan Sara Philipose and Sarasija P.BReferences1 I. Gutman, Selected Properties of the Schultz Molecular TopologicalIndex, J. Chem.Inf. Comput. Sci., 34 (1994) 1087-1089.2 J. A Bondy, U.S.R Murty, Graph Theory with Application, Macmil-lian Press, London(1976).3 J. Baskar Babujee, S. Ramakrishnan, Applied Mathematical Sci-ences, Vol. 6, no. 108(2012) 5383-5401.4 W. Klotz and T. Sander, Some properties of unitary Cayley graphs,The Electronic Journal of Combinatorics, 14 (2007) 1-12.5 Zhihui Cui,Bolian Liu, On Harary Matrix, Harary Index and HararyEnergy, MATCH Commun. Math. Comput. Chem., 68 (2012) 815-823.