Ratio Mathematica Volume 47, 2023 Transit in Corona product of graphs Reshmi KM* Raji Pilakkat† Abstract For a graph G(V, E), the transit of a vertex v is defined as the sum of the lengths of all geodesics with v as an internal vertex. This pa- per deals with the transit of vertices in Corona product of graphs. We obtain expressions for transit of an arbitrary vertex in the Corona product G1 ◦ G2 of G1 and G2. We also consider the cases where G1 is a particular graph class. The expressions for transit of vertices in G1 ◦ G2, with G1 as path Pn, a cycle Cn, a star Sn, a complete graph Kn and a complete bipartite graph Km,n is established. Keywords: Geodesic, Transit Index, Transit Identical, Corona prod- uct 2020 AMS subject classifications: 05C10, 05C12 1 *Govt. Arts and Science College, Kozhikode, Kerala-673018, India); reshmikm@gmail.com. †University of Calicut, Malappuram, India-673365; rajipilakkat@gmail.com. 1Received on September 24, 2022. Accepted on June 18, 2023. Published on June 30, 2023. DOI: 10.23755/rm.v39i0.860. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 260 Reshmi K M, Raji Pilakkat 1 Introduction Topological indices and centrality measures are graph invariant. Numerous studies have been carried out in these areas. The first notable topological index was the wiener index, named after Harry Wiener, a pioneer in chemical graph theory. It is defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representing the non-hydrogen atoms in the molecule. Wiener made fundamental contributions to the study of topolog- ical indices and established a correlation between the Wiener index and boiling points (hence viscosity and surface tension) of the paraffin. He could establish relationships with many chemical properties of alkanes with the wiener index. Centrality measures are a vital tool for understanding graphs. Each measure has its own definition of importance. Some are based on the degree of a vertex while others take the closeness to other vertices as the score of significance. In the paper [Shimbel and Alfonso], they introduced the concept of the stress of a vertex. It is the number of shortest paths on which a vertex lies. This was further modified to produce measures of centrality. It found applications in social networking, for analyzing communication dynamics. Keeping in mind the above two concepts, we introduced a new index, called the transit index of a graph. It considers the distances in the graph as well as the degree of vertices. In computing the stress of a vertex, we only take into account the number of shortest paths through it; the length of the paths is not considered. Be it in data transmission or in the measure of closeness, the length of the paths also matters. Hence, in the computation of transit we account for the number of shortest paths as well as their length. Graph products are binary operations. Two graphs G1 and G2 are combined to produce a new graph H. In this paper, we study the transit of vertices in the Corona product of graphs. Information on individual graphs is used to compute the transit of vertices in their Corona products. Thus the transit of vertices in large graphs and networks, which can be viewed as Corona products of simple graphs, can be computed more efficiently. 2 Preliminaries In this section, we come across certain definitions and terminologies employed in developing results in the latter sections. Throughout this paper we only consider simple connected and finite graphs. Definition 2.1 (K.M.Reshmi and Pilakkat. Raji [2020]). Let v ∈ V . Then the transit of v denoted by T(v) is “the sum of the lengths of all shortest paths with v 261 Transit in Corona product of graphs as an internal vertex” and the transit index of G denoted by TI(G) is TI(G) = ∑ v∈V T(v) Lemma 2.2 (K.M.Reshmi and Pilakkat. Raji [2020]). T(v) = 0 iff ⟨N[v]⟩ is a clique. Theorem 2.3 (K.M.Reshmi and Pilakkat. Raji [2020]). For a path Pn, Transit index is TI(Pn) = n(n + 1)(n2 − 3n + 2) 12 Theorem 2.4. For a cycle, the transit of any vertex v is, T(v) = (n 2−4)n 24 and i) TI(Cn) = n2(n2−4) 24 ,n even. ii) TI(Cn) = n(n2−1)(n−3) 24 , n odd Definition 2.5. Two vertices of a graph are called transit identical if the shortest paths passing through it are same in number and length. We use the following terminologies. The order of a graph G, denoted by |G| is the number of vertices in V (G). The distance between two vertices u, v ∈ V is the length of any shortest u − v path in G. A shortest path from u to v is also called a u − v geodesic. The number of shortest u − v paths is denoted by σ(u, v) and the number of shortest u − v path with ’a’ as an internal vertex is denoted by σ(u, v/a). It can be noted that a vertex ’a’ lies on a shortest u − v path iff d(u, v) = d(u, a) + d(a, v). The number of shortest u − v path with ’a’ as an internal vertex can be computed as σ(u, v/a) = σ(u, a) × σ(a, v). Number of shortest paths in G with ’a’ as an internal vertex is denoted by σG(a). Clearly σG(a) = ∑ (u,v) σ(u, v/a) 3 Transit of vertices in Corona Product of graphs 3.1 Corona Product of Graphs Definition 3.1. (Frucht and Harary [1970]) Let G1 and G2 be two graphs. The corona product G1 ◦ G2, is obtained by taking one copy of G1 and |V (G1)| copies of G2; and by joining each vertex of the i-th copy of G2 to the i-th vertex of G1, where 1 ≤ i ≤ |V (G1)| 262 Reshmi K M, Raji Pilakkat Whenever we consider G1 ◦ G2, we use the following notations. 1. Gi2 the ith copy of G2 in G1 ◦ G2 2. V (G1) = {u1, u2, . . . , un1}, |E(G1)| = m1 3. V (Gi2) = {vi1, vi2, . . . , vin2}, |E(G i 2)| = m2, ∀i Lemma 3.2. (Agnes [2015]) Let G1 and G2 be two arbitrary graphs. Then, • dG1◦G2(ui, up) = dG1(ui, up), 0 ≤ i, p ≤ n1 • dG1◦G2(ui, v p q) = dG1(ui, up) + 1, 0 ≤ i, p ≤ n1, 0 ≤ q ≤ n2 • dG1◦G2(v i j, v p q) =   dG1(ui, up) + 2, i ̸= p 1, if i = p, vjvq ∈ E(G2) 2, if i = p, vjvq /∈ E(G2) Proposition 3.3. For any two graphs G1 and G2, 1. TG2(a) = 0 iff TG1◦G2(a) = 0, a ∈ G2 2. TG2(a) = TG1◦G2(a), for a ∈ G2 iff every shortest path in G2 with ’a’ as an internal vertex is of length 2. Proof. Note that as the result 2 is obvious, we prove only 1. 1) TG2(a) = 0 ⇐⇒ ⟨NG2[a]⟩ is a clique. ⇐⇒ ⟨NG1◦G2[a]⟩ is a clique⇐⇒ TG1◦G2(a) = 0. Proposition 3.4. Let G1 and G2 be arbitrary graphs, 1)For any up in G1, σG1◦G2(up) = (n2 + 1) [ (n2 + 1)σG1(up) + n2 ∑n1 p̸=k=1 σG1(up, uk) ] 2) σG1◦G2(v i k) = Number of geodesic of length 2 in G2 with vk as an internal vertex. Proof. 1)Let up be any vertex of G1. Every geodesic in G1 with up as an internal vertex will be counted in σG1◦G2(up). For k ̸= l, geodesics connecting Gk2 ∪{uk} to Gl2 ∪{ul} will have ul −uk geodesic as its part. Let P1 be one of the ul − uk geodesic with up as an internal vertex. Then P1 will be part of a geodesic connecting vertices of Gk2 ∪ {uk} to vertices of Gl2 ∪ {ul}. There will be - n22 geodesics connecting G k 2 to G l 2, - n2 geodesics connecting Gk2 to ul and 263 Transit in Corona product of graphs - n2 geodesics connecting Gl2 to uk, with P1 as its part. Hence for the pair of vertices (uk, ul), there will be (n22 + 2n2 + 1)σG1(up) geodesics with up as an internal vertex. The geodesics connecting vertices of Gp2 to other vertices of G1 ◦ G2 will have up − uk geodesic as a part for some k. If P2 is one of the up − uk geodesic, it will be part of - n22 geodesics connecting G k 2 to G p 2 and - n2 geodesics connecting G p 2 to uk. Hence for every up − uk geodesic in G1 there will be σG1(up, uk)[n2(n2 +1)] geodesics in G1 ◦G2 with up as an internal vertex. Considering every pair uk − up the result follows. 2) Since every vertex of Gi2 are joined to ui, the maximum distance between ver- tices of Gi2 is 2. Hence the proof. Next we find an expression for the transit of a vertex, up in G1 ◦ G2, where G1 and G2 are arbitrary. Let (uk, ul) be a pair of vertices in G1 such that uk − ul geodesic has up as an internal vertex. Let Tkl(up) denote the contribution to transit of up, due to geodesic connecting vertices of Gk2 ∪ {uk} to Gl2 ∪ {ul}. Also we denote the contribution of vertices in Gp2 to T(up) by Tp(up). Lemma 3.5. For arbitrary graphs G1 and G2, Tkl(up) = σG1(uk, ul/up) [ (n2 + 1) 2d(uk, ul) + 2n2(n2 + 1) ] Proof. Table 1 gives the length and number of geodesics through up Vertices connected Length Number Gk2 to G l 2 2 + d(uk, ul) n 2 2σ(uk, ul/up) uk to Gl2 1 + d(uk, ul) n2σ(uk, ul/up) Gk2 to ul 1 + d(uk, ul) n2σ(uk, ul/up) uk to ul d(uk, ul) σ(uk, ul/up) Table 1: Table detailing geodesics through up The result follows. Lemma 3.6. Tp(up) = ∑n1 p ̸=k=1 [ σG1(up, uk) [ n2(n2+1)d(up, uk)+n2(1+2n2) ]] + 2 [( n2 2 ) − m2 ] Proof. Table 2 gives the contribution of geodesics through up to Tp(up). Consid- ering every vertex uk, k ̸= p, the result follows. Theorem 3.7. 1) T(up) = Tp(up) + ∑ kl Tkl(up) 2) T(vpi ) = 2× number of geodesics in G2 of length 2 through vi. 264 Reshmi K M, Raji Pilakkat Vertices connected Length Number uk to G p 2 1 + d(uk, up) n2σ(uk, up) Gk2 to G p 2 2 + d(uk, up) n 2 2σ(uk, up) G p 2 to G p 2 2 ( n2 2 ) − m2 Table 2: Geodesics through up Proof. 1) Geodesics through up are either considered in Tp(up) or in Tkl(up). Hence the result is evident. 2) Follows from Proposition 3.4. In the remaining sections we consider G2 as arbitrary, while G1 is replaced by various graph classes like Pn, Cn, Kn, Km,n and Sm+1 3.2 Path Graphs Let Pn be the path graph with vertices 1, 2, . . . , n. We give an expression for transit of k using Theorem 3.7 in Pn ◦ G2. Theorem 3.8. T(k) = (k − 1)(n2 + 1)(n − k) 2 [ (n2 + 1)(n + 1) + 4n2 ] + n2(n2+1) [(k − 1)k 2 + (n − k)(n − k + 1) 2 ] +n2(2n2+1)(n−1)+2 [(n2 2 ) −m2 ] Proof. Let 1 ≤ l < k < m ≤ n. Since G1 is a path, we have σG1(l, m/k) = 1. Hence Tlm(k) = (n2 + 1)2(m − l) + 2n2(n2 + 1) ∴ ∑ l,m Tlm(k) = (n2 + 1) 2 k−1∑ l=1 n∑ m=k−1 (m − l) + k−1∑ l=1 n∑ m=k−1 2n2(n2 + 1) = (n2 + 1) 2TG1(k) + (k − 1)(n − k − 1)2n2(n2 + 1) = (n2 + 1) 2 (n + 1)(k − 1)(n − k) 2 + (k − 1)(n − k − 1)2n2(n2 + 1) = (k − 1)(n2 + 1)(n − k) 2 [ (n2 + 1)(n + 1) + 4n2 ] 265 Transit in Corona product of graphs In a similar manner we compute Tk(k) Tk(k) = n∑ k ̸=i=1 [ (d(k, i) + 1)n2 + (d(k, i) + 2)n 2 2 ] +2 [(n2 2 ) − m2 ] = (n2 + n 2 2) [ (k − 1)k 2 + (n − k)(n − k + 1) 2 ] + n2(2n2 + 1)(n − 1) +2 [(n2 2 ) − m2 ] The result follows. In the following examples we compute transit for the vertices in various corona product of Pn. From Theorem 3.8, we have T(k) = (k − 1)(n2 + 1)(n − k) 2 [ (n2 + 1)(n + 1) + 4n2 ] +n2(n2+1) [(k − 1)k 2 + (n − k)(n − k + 1) 2 ] +n2(2n2+1)(n−1)+2 [(n2 2 ) −m2 ] = T1 + T2, say where T2 = 2 [( n2 2 ) − m2 ] Examples 1. G2 = Pm. Here n2 = m, m2 = m−1. Hence T(k) = T1 +(m−1)(m−2). For pendant vertices of P im, the transit is 0 and 2 for others, ∀i. 2. G2 = Cm. Here n2 = m2 = m. For every vertex in Cim, there exist only one geodesic of length 2 through it. Here T(k) = T1 + m(m − 3) and T(vik) = 2, ∀k, i. 3. G2 = Km. Then n2 = m, m2 = ( m 2 ) . Thus, T(k) = T1 and T(vik) = 0, ∀k, i. 4. G2 = Sm. Here n2 = m, m2 = m−1. Hence T(k) = T1 +(m−1)(m−2). T(vik) = 0, for pendant vertices and for central vertex of S − m, T(v i k) = (m − 1)(m − 2) 5. G2 = Kl1,l2 . n2 = m = l1 + l2 and m = l1l2 T(k) = T1 + (m − 1)m − 2l1l2 and T(vik) = TKl1,l2 (vk) 266 Reshmi K M, Raji Pilakkat 3.3 Cycle In this section we consider G1 to be a cycle. We have already seen that transit of vertices in cycles with order 2n and 2n + 1 are the same. Hence we consider G1 = C2n1+1. We represent the vertices by 0, 1, . . . , 2n1. Also every vertex in the cycle being transit identical, it is enough we compute the transit for n1. Theorem 3.9. If a is any vertex of the cycle C2n or C2n+1, its transit in the corona product C2n ◦ G2 or C2n+1 ◦ G2 is given by T(a) = (n2+1)(n1−1)n1 3 [n2n1 + 4n2 + n1 + 1] + n2n1 [ (n2 + 1)(n1 + 1) + 2(1 + 2n2) ] + 2 [( n2 2 ) − m2 ] Proof. For any k, l we know that σG1(k, l/n1) = 1. Tk,l(n1) = [ (n2 + 1) 2d(k, l) + 2n2(n2 + 1) ] ∴ ∑ k,l Tk,l(n1) = (n2 + 1) 2 ∑ k,l d(k, l) + n1(n1 − 1) 2 2n2(n2 + 1) = (n2 + 1) 2TG1(n1) + n1(n1 − 1) 2 2n2(n2 + 1) = (n2 + 1) 2 (n 2 − 1)n 24 + n1(n1 − 1) 2 2n2(n2 + 1) = (n2 + 1)(n1 − 1)n1 3 [n2n1 + 4n2 + n1 + 1] Next we compute Tn1(n1) Tn1(n1) = 2n1∑ n1 ̸=i=0 [ n2(n2 + 1)d(n, i) + n2(1 + 2n2) ] +2 [( n2 2 ) − m2 ] , σG1(n1, i) being 1 = n2n1 [ (n2 + 1)(n1 + 1) + 2(1 + 2n2) ] + 2 [( n2 2 ) − m2 ] And TG1◦G2(n1) = ∑ k,l Tk,l(n1) + Tn1(n1). Hence the proof. 3.4 Star Let G1 = Sn+1. In a star there are n pendant vertices and one central vertex. All pendant vertices are transit identical. Hence we need to compute transit of one of the pendant vertex and the central vertex in Sn+1 ◦G2. Let us name the vertices as 1, 2, . . . , n + 1, where n + 1 is the central vertex. 267 Transit in Corona product of graphs Theorem 3.10. In Sn+1 ◦ G2, T(n + 1) = n [ (n − 1)(n2 + 1)(2n2 + 1) + n2(3n2 + 2) ] + 2 [( n2 2 ) − m2 ] and T(i) = n2 [ (n2 + 1)(2n − 1) + n(2n2 + 1) ] + 2 [( n2 2 ) − m2 ] , i ̸= n + 1 Proof. Consider n + 1. We have σ(k, l/(n + 1)) = 1 and d(k, l) = 2 Thus Tk,l(n + 1) = 2(n2 + 1)(2n2 + 1) (1) ∴ ∑ k,l Tk,l(n + 1) = ( n 2 ) 2(n2 + 1)(2n2 + 1) (2) = n(n − 1)(n2 + 1)(2n2 + 1) (3) While computing Tn+1(n + 1), we see that σSn+1(n + 1, i) = 1 and d(n + 1, i) = 1, ∀i. Thus we get Tn+1(n+1) = nn2(3n2 +2)+2 [( n2 2 ) − m2 ] , which completes the computation for T(n + 1) Now consider the vertex i ̸= n + 1. It can easily be verified that σ(k, l/i) = 0, ∀k, l. Hence ∑ k,l Tk,l(i) = 0. for a fixed i, σ(i, k) = 1∀k and d(i, n + 1) = 1 and d(i, k) = 2, k ̸= n + 1 ∴ Ti(i) = n2 [ 4nn2 + 3n − n2 − 1 ] + 2 [( n2 2 ) − m2 ] . Hence the proof. 3.5 Complete graph and Complete bipartite graph Theorem 3.11. In the corona product Kn ◦ G2, the transit of any vertex of Kn is (n − 1)n2(3n2 + 2) + 2 [( n2 2 ) − m2 ] Proof. Since every vertex of Kn is transit identical, we consider one of them. Let ui be any vertex of Kn. σ(uk, ul/ui) = 0 =⇒ ∑ Tk,l(ui) = 0 Again σ(ui, uk) = 1, ∀k ̸= i and d(ui, uk) = 1 ∴ Ti(ui) = ∑ k ̸=i [ n2(n2 + 1) + n2(2n2 + 1) ] + 2 [( n2 2 ) − m2 ] . Hence the result. Next we consider a complete bipartite graph Kl1,l2 with bipartition V1, V2. Let V1 = a1, a2, . . . , al1 and V2 = b1, b2, . . . , bl2 . Then all ai are transit identical. Similarly all bi are also transit identical. Computation of T(ai) and T(bi) are similar. Hence we compute T(ai) only. Theorem 3.12. In Kl1,l2 ◦ G2, the transit of ai, T(ai) = ( l2 2 ) 2(n2 + 1)(2n2 + 1) + l2n2(4n2 + 3)(l1 − 1) + l2n2(3n2 + 2) + 2 [( n2 2 ) − m2 ] Proof. The shortest path in Kl1,l2 through ai are those connecting vertices of V2. ∴ Tk,l(ai) = σKl1,l2 (bk, bl/ai) [ (n2 + 1) 2d(uk, ul) + 2n2(n2 + 1) ] . Thus∑ k,l Tk,l(ai) = ( l2 2 ) 2(n2 + 1)(2n2 + 1). 268 Reshmi K M, Raji Pilakkat While computing Ti(ai), we see that vertices in V1 and V2 behaves differently. Hence we split the summation as follows. Ti(ai) = ∑ aj σ(ai, aj) [ n2(n2 + 1)d(ai, aj) + n2(2n2 + 1) ] + ∑ bj σ(ai, bj) [ n2(n2 + 1)d(ai, bj) + n2(2n2 + 1) ] + 2 [( n2 2 ) − m2 ] = l2n2(4n2 + 3)(l1 − 1) + l2n2(3n2 + 2) + 2 [( n2 2 ) − m2 ] 4 Conclusion In this paper, we first considered arbitrary graphs G1 and G2. We could give an expression for the transit of vertices in their corona product. This result was applied to compute the transit of vertices in G1/circG2, where G1 refers to a particular graph. It should be noted that we could express the transit of vertices in G1 ◦ G2 in terms of individual graph parameters. Thus, the computation of transit in huge networks, which are Corona products, is now much easier. References V. Agnes. Degree distance and gutman index of corona product of graphs. Trans- actions on combinatorics, 4, 2015. J. Bondy and U. Murty. Graph Theory. Springer, 2019. R. Frucht and F. Harary. On the corona of two graphs. Aeq. Math., 4:322–325, 1970. doi: https://doi.org/10.1007/BF01844162. P. S. Gajendra, A. Borah, and S. Ray. A review paper on corona product of graphs. Advances and Applications in Mathematical Sciences, 19:1047–1054, 2020. H. Harary. Graph Theory. Addison Wesley, 1969. K.M.Reshmi and Pilakkat. Raji. Transit index of a graph and its correlation with mon of octane isomers. Advances in Mathematics: Scientific Journal, 9, 2020. doi: https://doi.org/10.37418/amsj.9.4.39. 269 Transit in Corona product of graphs Shimbel and Alfonso. Structural parameters of communication networks. Bulletin of Mathematical Bio- physics, 15:501–507. Wagner.S and Wang.H. Introduction to chemical graph theory. Taylor and Francis Group, Boca Raton, FL : CRC Press, 2019. 270