EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 3, 2023, 1406-1420 ISSN 1307-5543 – ejpam.com Published by New York Business Global Closeness Centrality of Vertices in Graphs Under Some Operations Farene Loida Alfeche1, Victor Barraza2,∗, Sergio Canoy, Jr.1,3 1 Department of Mathematics and Statistics, College of Science and Mathematics, MSU- Iligan Institute of Technology, 9200 Iligan City, Philippines 2 Department of Arts and Sciences, College of Teacher Education Arts and Sciences, Visayas State University Alangalang, Alangalang, Leyte, Philippines 3 Center for Mathematical and Theoretical Physical Sciences-PRISM, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. In this paper, we revisit the concept of (normalized) closeness centrality of a vertex in a graph and investigate it in some graphs under some operations. Specifically, we derive formulas to compute the closeness centrality of vertices in the shadow graph, complementary prism, edge corona, and disjunction of graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Closeness centrality, shadow graph, edge corona, complementary prism, disjunction 1. Introduction According to a study in [7], centrality is one of the most studied subjects in the analysis of social networks. As mentioned in [4], the concept was developed by social scientists some decades ago with the aim of quantifying an intuitive perception that some nodes or linkages are regarded central according to some criteria in many particular networks or graphs. For example, in a social network which is often represented as a graph, where each individual is represented as a vertex, the relationship between pairs of individuals are connected by edges, and the weights on the edges indicate the strength of the relationships, centrality gives a way of determining how central an individual is located in this network (see [6]). Within graph theory and network analysis, some of the common measurements of centrality pointed out in [8] are degree centrality, closeness centrality, eigen vector centrality, and betweeness centrality. One may also refer to [1], [2], and [5] for some studies in measure of centrality. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v16i3.4848 Email addresses: fareneloida.alfeche@g.msuiit.edu.ph (F. Alfeche), victor.barraza@vsu.edu.ph (V. Barraza), sergio.canoy@g.msuiit.edu.ph (S. Canoy) https://www.ejpam.com 1406 © 2023 EJPAM All rights reserved. F. Alfeche, V. Barraza, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1406-1420 1407 Closeness centrality measures how close a vertex is to all other vertices in a graph. The closeness centrality of a vertex in a graph is the inverse of the average geodesic distance from the vertex to any other vertex in the graph. The greater value of closeness centrality of a vertex would mean a better position of a vertex in spreading information to other vertices (see [6]). A study on closeness centrality can be found in [4] where the authors derived the closeness centrality of vertices of some families of graphs such as paths, cycles, fans, wheels, complete bipartite graphs, and complete split graphs. In a more recent study, Eballe et al. in [3] presented the closeness centrality of the vertices in the corona, Cartesian product and lexicographic product of graphs. In this paper, we derive formulas of the closeness centrality of a vertex in the shadow graph, edge corona of graphs, complementary prism, and disjunction of graphs. 2. Terminology Definition 1. Let G be a connected graph and let u, v ∈ V (G). The distance between u and v, denoted by dG(u, v), is the length of a shortest path (called u-v geodesic) connecting u and v. Vertices u and v are adjacent or neighbors (i.e. uv ∈ E(G)) if and only if dG(u, v) = 1. The open neighborhood of v is the set NG(v) = {w ∈ V (G) : dG(v, w) = 1} and its closed neighborhood is the set NG[v] = NG(v) ∪ {v}. Definition 2. Let G be a connected graph. If v ∈ V (G) and e ∈ E(G), then the distance dG(v, e) between v and e, is given by dG(v, e) = min x∈V (G) {dG(v, x), dG(v, x)}. Definition 3. Let G = (V (G), E(G)) be a nontrivial connected graph of order m. If u ∈ V (G), then the closeness centrality of vertex u is given by CG(u) = m− 1 TG(u) , where TG(u) = ∑ x∈V(G) dG(u,x). Definition 4. The shadow graph S(G) of G is the graph obtained by taking two copies of G, say G1 and G2, and then joining each vertex v ∈ V (G1) to the neighbors of v′ ∈ V (G2), where v′ is the vertex in V (G2) corresponding to v, i.e., v and v′ represent the same vertex in G. F. Alfeche, V. Barraza, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1406-1420 1408 .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ................................................................................................................................................................................................. ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ................................................................................................................................................................................................. ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ................................................................................................................................................................................................. ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ................................................................................................................................................................................................. ....................................................................................................................................................................................................................................................................................................................... ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ......................... .............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .... .................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ................................. ......................... ................... .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .................. .... ....................................................................................................................................................................................................................................................................................................................... v1 v2 v3 v4 v′1 v′2 v′3 v′4 G1 = C4 G2 = C4 Figure 1: The shadow graph S(C4) of C4 Definition 5. Let G and H be two graphs. The edge corona G ⋄ H of G and H is the graph obtained by taking one copy of G and |E(G)| copies of H, and then joining two end-vertices of the i-th edge of G to every vertex in the i-th copy of H. For every edge e = uv of G, denote by He = Huv the copy of H where vertices are joined to the vertices u and v. .................................... .................................... .................................... .................................... .................................... .............. ............. ............. ............. ............. ............. ............. .......... ...................................................................................... ............................................................................ .... ......... ......... ......... ......... ......... ......... ......... ......... ......... . ...................................................................................................... .............. ............. ............. ............. ......... .................................... .................................... .............................................................. .................................... .................................... ................................................................................... .................................... ................................................. .................................... .................................... .......... ......... ......... ......... ......... ... . ................................... .................................... ................................. ................................ ................................ ........... ................................................. ............................................................................................................ ................................. ................ ................................................... ......... ......... ......... ......... ......... ......... ......... ........ ............... .............. ............. ......... ........ ........ ........ ........ ........ ........ ........ ...... ............................................................................................................................................. ................................... .......................................................................................... ................ ................ ................ ........ .......... ......... ......... ....... ............... .............. .............. .............. .............. .............. ........ ................................................ .......................................... ....................................................................... ........... .......... .......... .......... . ................................................................................ Figure 2: The edge corona C5 ⋄ P2 Definition 6. The complementary prism of graph G, denoted by GG, is the graph ob- tained from the disjoint union of G and G by adding the edges vv, where v ∈ V (G) and v is the vertex of G corresponding to vertex v. Figure 3: The complementary prism C5C5 F. Alfeche, V. Barraza, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1406-1420 1409 Definition 7. The disjunction of graphs G and H, denoted by G ∨H, is the graph with V (G ∨ H) = V (G) × V (H) and (x, p)(y, q) ∈ E(G ∨ H) if and only if xy ∈ E(G) or pq ∈ E(H). 3. Main Results In what follows, G1 and G2 are the copies of G in the shadow graph S(G). Remark 1. Let G be a graph and let v, w ∈ V (G1). Then dS(G)(v, w) = dG1(v, w) = dG2(v ′, w′) = dS(G)(v ′, w′). Lemma 1. Let G be a nontrivial connected graph. For each p ∈ V (G1) and v′ ∈ V (G2), dS(G)(p, v ′) = dS(G)(p ′, v) = { 2 if p = v dG1(p, v) if p ̸= v. Proof. If p = v, then p′ = v′ and pp′ /∈ E(S(G)). Let w ∈ NG1(p). Then wp′ ∈ E(S(G)). Hence, [p, w, v′] is a p− v′ geodesic in S(G). This implies that dS(G)(p, v ′) = 2. Next, suppose that p ̸= v, that is, p′ ̸= v′. Let [p1, p2, ..., pk], where p = p1 and v = pk, be a p-v geodesic in G1. Then [p′1, p ′ 2, ..., p ′ k] is a p′-v′ geodesic in G2. Also, by definition of S(G), [p1, p ′ 2, p ′ 3..., p ′ k] is a p-v′ geodesic in S(G). Hence, dS(G)(p, v ′) = dG1(p, v). Since dG1(p, v) = dG2(p ′, v′), it follows that dS(G)(p, v ′) = dS(G)(p ′, v). Consider the shadow graph S(P5) in Figure 4. .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ................................................................................................................................................................................................. ................................................................................................................................................................................................. ................................................................................................................................................................................................. ............................................................................................................................................................................................................. ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... p′ p v′ v G2 G1 Figure 4: The shadow graph S(P5) Clearly, dS(G)(p, p ′) = 2, and dS(G)(p, v) = dS(G)(p, v ′) = dS(G)(p ′, v′) = 3. Theorem 1. Let G be a non-trivial connected graph. For each p ∈ V (G1), τS(G)(p) = 2(τG1(p)) + 2 and τS(G)(p ′) = 2(τG2(p ′)) + 2. F. Alfeche, V. Barraza, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1406-1420 1410 Proof. Let p ∈ V (G1). Then τS(G)(p) = ∑ q∈V (S(G)) dS(G)(p, q) = ∑ q∈V (G1) dS(G)(p, q) + ∑ v′∈V (G2) dS(G)(p, v ′) = ∑ q∈V (G1) dG1(p, q) + ∑ v′∈V (G2)−{p′} dS(G)(p, v ′) + dS(G)(p, p ′) = τG1(p) + ∑ v∈V (G1)−{p} dG1(p, v) + 2 = 2τG1(p) + 2. Similarly, τS(G)(p ′) = 2τG2(p ′) + 2. The next result follows from Theorem 1 and Definition 3. Corollary 1. Let G be a non-trivial connected graph of order m and let p ∈ V (G1). Then CS(G)(p) = 2m− 1 2(τG1(p)) + 2 and CS(G)(p ′) = 2m− 1 2(τG2(p ′)) + 2 . Example 1. Consider the shadow graph S(P5) in Figure 5, where G = P5. .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ..................................................................................................................................... ................................................................................................................................................................................................. ................................................................................................................................................................................................. ................................................................................................................................................................................................. ............................................................................................................................................................................................................. ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ..... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .....• p′ G2 G1 Figure 5: The shadow graph S(P5) and p′ ∈ V (G2) Then m = 5 and τG2(p ′) = 7. Using Corollary 1, the closeness centrality of p′ is CS(G)(p ′) = 2m− 1 2τG2(p ′) + 2 = 2(5)− 1 2(7) + 2 = 10− 1 14 + 2 F. Alfeche, V. Barraza, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1406-1420 1411 = 9 16 . For a non-trivial connected graph G and v ∈ V (G), the set Ev is given by Ev = {xv ∈ E(G) : x ∈ V (G) \ {v}}. Theorem 2. Let G and H be non-trivial connected graphs. If v ∈ V (G), then τG⋄H(v) = τG(v) + |V (H)||E(G)|+ |V (H)| ∑ e∈E(G)\Ev dG(v, e). Proof. Let v ∈ V (G). Then |Ev| = |NG(v)| and dG⋄H(v, a) = dG(v, e) + 1 for every a ∈ V (He) where e ∈ E(G) \ Ev. Hence, τG⋄H(v) = ∑ x∈V (G) (dG(v, x)) + ∑ e∈Ev ∑ a∈V (He) dG⋄H(v, a) + ∑ e∈E(G)\Ev ∑ a∈V (He) dG⋄H(v, a) = τG(v) + |Ev||V (H)|+ ∑ e∈E(G)\Ev [(dG(v, e) + 1)|V (H)|] = τG(v) + |Ev||V (H)|+ |V (H)| ∑ e∈E(G)\Ev dG(v, e) + |V (H)||E(G)| − |Ev||V (H)| = τG(v) + |V (H)||E(G)|+ |V (H)| ∑ e∈E(G)\Ev dG(v, e). The next result is immediate from Theorem 2. Corollary 2. Let G and H be connected non-trivial graphs with m = |V (G)|, r = |E(G)|, and n = |V (H)|. If v ∈ V (G), then CG⋄H(v) = m+ rn− 1 τG(v) + rn+ n ∑ e∈E(G)\Ev dG(v, e) . Example 2. Consider the edge corona of G = C4, H = P5, and v ∈ V (G) in Figure 6. Then m = |V (G)| = |E(G)| = r = 4, n = |V (H)| = 5, τG(v) = 4, |Ev| = |E(G) \ Ev| = 2 and ∑ e∈E(G)\Ev dG(v, e) = 2. Using Corollary 2, the closeness centrality of v ∈ V (G) is CG⋄H = m+ qn− 1 τG(v) + nq + n ∑ e∈E(G)\Ev dG(v, e) = 24− 1 4 + (5)(4) + (5)(2) F. Alfeche, V. Barraza, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 16 (3) (2023), 1406-1420 1412 .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .................................................................................................................................................................. .... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ...... .................................................................................................................................................................. .......................................... ........... .......... .......... .......... . .......................................... ........... .......... .......... .......... . .......... ......... ......... ......... ......... ......... ......... ......... ....... .............. ............. ............. ............. ......... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........................ ....................... ....................... ....................... ................... ................. ................ ................ ................ ................ ................ ................ ................ ................ ......................................................................................................................................................................... ................................................................................................................ ............................................................................................................... .............................................................. ................................................................................ ........... .......... .......... .......... . .......................................... ........... .......... .......... .......... . .......................................... ................................................................................ .............................................................. ............................................................................................................... ................................................................................................................ .............................................................................................................................................................................. ................ ................ ................ ................ ................ ................ ................ ................ ............ ........................ ....................... ....................... ....................... ................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .............. ............. ............. ............. ......... .......... ......... ......... ......... ......... ......... ......... ......... ....... ............... .............. ............. .......................................... ............... .............. ............. .......................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .......... .......... .......... .......... .......... . .......................... ......................... ......................... .... ................................................................................ .............................................................. ............................................................................................................... ................................................................................................................ ............................................................................................................................................................. ............... .............. ............. .......................................... ............... .............. ............. .......................................... ................................................................................ .............................................................. ............................................................................................................... ................................................................................................................ ............................................................................................................................................................. ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .......... .......... .......... .......... .......... . .......................... ......................... ......................... .... •v Figure 6: The edge corona graph C4 ⋄ P5 and v ∈ V (C4) = 23 34 . For a non-trivial connected graphG and e = uv ∈ E(G), the sets Vu≤v, Vv