EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 14, No. 1, 2021, 248-264 ISSN 1307-5543 – ejpam.com Published by New York Business Global A Breadth-first Search Tree Construction for Multiplicative Circulant Graphs John Rafael M. Antalan1,2,∗, Francis Joseph H. Campeña2 1 Department of Mathematics and Physics, College of Science, Central Luzon State University, Science City of Muñoz, 3120 Nueva Ecija, Philippines 2 Mathematics and Statistics Department, College of Science, De La Salle University, 2401 Taft Avenue, Malate, Manila, 1004 Metro Manila, Philippines Abstract. In this paper, we give a recursive method in constructing a breadth-first search tree for multiplicative circulant graphs of order power of odd. We then use the proposed construction in reproving some results concerning multiplicative circulant graph’s diameter, average distance and distance spectral radius. We also determine the graph’s Wiener index, vertex-forwarding index, and a bound for its edge-forwarding index. Finally, we discuss some possible research works in which the proposed construction can be applied. 2020 Mathematics Subject Classifications: 05C09, 05C12, 05C25, 05C50, 05C85 Key Words and Phrases: Breadth-first search tree, multiplicative circulant graph, graph distance matrix, graph diameter, graph distance spectral radius, graph average distance, Wiener index, graph edge-forwarding index, graph vertex-forwarding index 1. Introduction Let Γ be a simple connected graph with vertex set V (Γ) and edge set E(Γ). The number dΓ(vi, vj) denotes the distance between two vertices vi and vj of Γ, which is the number of edges in a shortest path between the vertices. For a fix vi ∈ V (Γ) and for any vj ∈ V (Γ), dΓ(vi, vj) can be determined using the Breadth-first Search Method or simply called bfs method. The pseudo-code for bfs method is given in the next page. When bfs method is applied to a particular vertex vi ∈ V (Γ) of the graph Γ, the result is a rooted tree with vertex vi as the root. This tree is called a bfs tree with root vi and is denoted by bfsvi(Γ). The rooted tree bfs0(C5) is shown in the right part of Figure 1. In a rooted tree, we call a vertex vi the parent of vertex vj and vertex vj a child of vertex vi if the edge (vi, vj) is an edge in a rooted tree; where the naming of an edge (vi, vj) is with respect to their level relative to the root. Also, a vertex vi is said to be an ancestor of vertex vj and vertex vj is a descendant of vertex vi if there is a path from vi to vj whose edges all go from parent to child. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v14i1.3884 Email addresses: jrantalan@clsu.edu.ph (J. Antalan), francis.campena@dlsu.edu.ph (F. Campeña) http://www.ejpam.com 248 c© 2021 EJPAM All rights reserved. J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 249 Breadth-first Search Algorithm [5] Input: Undirected graph Γ = (V (Γ), E(Γ)) and a vertex s ∈ V (Γ) Output: Breadth-first tree T from s. Vi = {all vertices at distance i from s} V0 = {s} make s the root of T i = 0 while Vi 6= ∅ do construct Vi+1 Vi+1 = ∅ for each vertex v ∈ Vi do “scan v” for each edge (v, w) do if w /∈ ⋃ j Vj then make w the next child of v in T add w to Vi+1 i = i+ 1 Figure 1: The graph C5 and its corresponding bfs tree for vertex 0. In the rooted tree of Figure 1, vertex 1 is the parent of vertex 2 and hence, vertex 2 is a child of vertex 1. Also, the vertices 1,2,3, and 4 are descendants of the root vertex 0. The bfs tree contains the distance information between the root and all the other ver- tices in V (Γ). For instance, for the graph C5 in the left part of Figure 1, its corresponding bfs tree rooted from 0-vertex shown in the right part of Figure 1 reveals that dC5(0, v) = 1 if v = 1, 4 and dC5(0, v) = 2 if v = 2, 3. For a tree with vertical axial symmetry such as the tree in Figure 1, we classify its vertices as to whether it is located on the left part or on the right part of the tree. For instance, the left part of the bfs tree of C5 with root vertex 0 denoted by L[bfs0(C5)] contains the vertices 1 and 2; while the right part of the bfs tree ofC5 with root vertex 0 denoted by R[bfs0(C5)] contains the vertices 3 and 4. The main goal of this paper is to present a method on constructing a bfs tree for multiplicative circulant graphs of order power of odd. We formally define multiplicative J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 250 circulant graph in the next paragraph. Multiplicative circulant graphs are special type of Cayley graphs. By definition, given a group G and a subset S of G−{e}, a graph Γ is a Cayley graph of G with connection (or jump) set S, written Γ = Cay(G,S) if V (Γ) = G and E(Γ) = {{g, sg} : g ∈ G, s ∈ S}. If G = 〈Zn,+n〉, then the graph Γ = Cay(G,S) is called the circulant graph with connection set S. If a circulant graph Cay(Zn, S) is such that n = mh and S = {m0,m1, . . . ,mh−1} where m and h are integers with bounds m > 1 and h ≥ 0, then Cay(Zn, S) is called a multiplicative circulant graph or MC graph for short. MC graphs will be denoted by MC(mh) or Γ(m h). MC graphs was originally defined by Stojmenovic [12] in 1997 when he studied a particular class of circulant graph called recursive circulant graph or RC graph that was introduced by Park and Chwa [11] in 1994. Both MC and RC graphs are a special class of generalized recursive circulant graph or GRC graph defined by Tang et al. [14] in 2012. In particular, MC graphs are GRC graphs in which each dimensions have identical bases. Figure 2 shows some examples of MC graphs. Figure 2: The graphs MC(52), MC(72) and MC(73) MC graphs and in general circulant graphs have vast applications in different fields of study; some of these fields include telecommunication networking [4], VLSI (Very-large- scale integration) design [8], and distributed computing [10]. In the definition of multiplicative circulant graph, let m be odd. The following are important observable properties of Γmh whose proofs follow from the definition of MC graph and the bfs method: (i) dΓ mh (0, i) = dΓ mh (0,mh − i) for all non-zero i ∈ V (Γmh). (ii) Let A = {mh−1 −mh−2,mh−1 −mh−3, . . . ,mh−1 −mh−h}. For each a ∈ A, we have dΓ mh (0, a) = dΓ mh−1 (0, a) + 1. (iii) Γmh is ancestor-preserving for parents m0,m1, . . . ,mh−2 in bfs0(Γmh). That is, for parents m0,m1, . . . ,mh−2, the ancestor-descendant relationship is the same for bfs0(Γmh−1) and bfs0(Γmh). J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 251 (iv) For b = 1, 2, . . . , m h−1−1 2 , we have dΓ mh−1 (0, b) = dΓ mh (mh−1,mh−1 + b). (v) For b = 1, 2, . . . , m h−1−1 2 , we have dΓ mh (mh−1,mh−1 ± b) = dΓ mh (2(mh−1), 2(mh−1)± b) = dΓ mh (3(mh−1), 3(mh−1)± b) ... = dΓ mh ( m− 1 2 (mh−1), m− 1 2 (mh−1)± b ) . In this paper, we give a recursive method on constructing the bfs tree for Γmh using the listed properties above. We then use the construction to reprove some known results about Γmh ’s diameter, average distance and distance spectral radius. We also determine the following graph-related properties for Γmh : Wiener index, vertex-forwarding index, and bounds for its edge-forwarding index. Finally, we discuss some possible research works in which the proposed construction can be applied. 2. Preliminaries In this section, we discuss in a brief, the necessary concepts and results that will be used in the discussion of our main results. The discussion includes graphs’ distance matrix, distance spectral radius, vertex and edge forwarding index, and Wiener index. In the following definitions and discussion, we assume that our graph Γ is of n number of vertices. We begin by defining the concept of distance matrix of a graph. Definition 1. The distance matrix of Γ denoted by D(Γ) = [Dij ] where Dij = { dΓ(vi, vj) if vi 6= vj 0 otherwise. Remark 1. Circulant graphs have circulant distance matrix [9]. The next series of graph concepts for Γ can be calculated once D(Γ) is known. Definition 2. The diameter of Γ, denoted by diam(Γ), is the maximum distance between any pair of vertices in Γ. Remark 2. diam(Γ) is the maximum entry in D(Γ). Definition 3. The transmission of vi in Γ denoted by TrΓ(vi), is the sum of distances from vi to all other vertices of Γ, that is TrΓ(vi) = ∑ vj∈V (Γ) dΓ(vi, vj). J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 252 Remark 3. TrΓ(vi) is the sum of the entries in the ith row of D(Γ). Definition 4. The Wiener index of Γ denoted by W (Γ) is defined by W (Γ) = ∑ {vi,vj}⊆V (Γ) dΓ(vi, vj). Remark 4. W (Γ) is the sum of all the entries in D(Γ) divided by 2. Definition 5. The average distance of Γ denoted by µ(Γ) is the average of all distances in Γ. In symbol µ(Γ) = ∑ {vi,vj}⊆V (Γ) dΓ(vi, vj)( n 2 ) . Remark 5. µ(Γ) = W (Γ)( n 2 ) . Definition 6. The largest eigenvalue of the distance matrix of Γ is called the distance spectral radius of Γ and is denoted by ρ(Γ). In terms of vertex transmission, a special name for a graph Γ with uniform vertex transmission is given in the next definition. Definition 7. A graph Γ is said to be s-transmission regular if TrΓ(vi) = s for every vi ∈ V (Γ). Remark 6. Since the distance matrix of a circulant graph is circulant, it follows that circulant graphs are transmission regular graphs with transmission-regularity TrΓ(v0). For transmission regular graphs such as circulant graphs, the calculation of distance spectral radius is simpler. Lemma 1 ([9]). Let Γ be a circulant graph. Then ρ(Γ) = TrΓ(v0). We now define the concept of graph’s vertex and edge forwarding index. To define them we need to define a series of interrelated concepts. Definition 8. A routing R of Γ is a set of n(n− 1) elementary paths (i.e. paths where no vertices appear more than once) R(x, y) specified for all ordered pairs (x, y) of vertices of Γ. Remark 7. The set of all possible routing in a graph Γ is denoted by R(Γ). For vertex-forwarding index we have Definition 9. Let R ∈ R(Γ) and x ∈ V (Γ). The load of a vertex x in R of Γ denoted by ξx(Γ, R) is the number of paths specified by R passing through x and admitting x as an inner vertex. J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 253 Definition 10. The vertex-forwarding index of Γ with respect to a routing R, denoted by ξ(Γ, R) is the maximum number of paths of R going through any vertex x in Γ. Hence ξ(Γ, R) = max{ξx(Γ, R) : x ∈ V (Γ)}. Definition 11. The vertex-forwarding index of Γ, denoted by ξ(Γ) is the minimum forwarding index over all possible routing of Γ. In symbol, ξ(Γ) = min{ξ(Γ, R) : R ∈ R(Γ)}. For edge-forwarding index we have Definition 12. The load of an edge e with respect to R, denoted by πe(Γ, R), is the number of the paths specified by R going through it. Definition 13. The edge forwarding index of a graph Γ with respect to a routing R, denoted by π(Γ, R) is the maximum number of paths specified by R going through any edge of Γ. Hence π(Γ, R) = max{πe(Γ, R) : e ∈ E(Γ)}. Definition 14. The edge-forwarding index of a graph Γ, denoted by π(Γ) is defined by π(Γ) = min{π(Γ, R) : R ∈ R(Γ)}. We end this section by giving the exact value of vertex-forwarding index and a bound for the edge-forwarding index of a graph Γ. They are given in the last two results for this section. Lemma 2 (Lemma 4.2 [9]). If Γ is a connected circulant graph of order n, then ξ(Γ) = ρ(Γ)− (n− 1). Lemma 3 (Lemma 4.5 [9]). If Γ is a connected r−regular circulant graph of order n, then 2ρ(Γ) r ≤ π(Γ) ≤ n+ ρ(Γ)− (2r − 1). 3. A bfs tree construction for Γmh It is evident from properties (i)-(v) that the construction of bfs0(Γmh) will be based on bfs0(Γmh−1). Also, from property (i) and the fact that for any x, y ∈ Zn and s ∈ S, we have if x + y = 0 then (x + s) + (y − s) = 0 and (x − s) + (y + s) = 0, we know that bfs0(Γmh) has a vertical axial-symmetry with respect to the 0-vertex. So we have a definition and a remark. J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 254 Definition 15. The left part of bfs0(Γmh) denoted by L[bfs0(Γmh)] refers to the vertices m0,m1, . . . ,mh−1, and their descendants. While the right part of bfs0(Γmh) denoted by R[bfs0(Γmh)] refers to the vertices mh −mh−1,mh −mh−2, . . . ,mh −mh−h, and their descendants. Remark 8. For odd intger m and positive integer h we have L[bfs0(Γmh)] = {1, 2, . . . , mh−1 2 } while R[bfs0(Γmh)] = {mh−1 2 + 1, m h−1 2 + 2, . . . ,mh − 1}. Using the five properties of Γmh presented in the introduction, a method for construct- ing bfs0(Γmh) based from bfs0(Γmh−1) is as follows: Method on Constructing bfs0(Γmh) Given bfs0(Γmh−1), bfs0(Γmh) can be constructed as follows: Step 1. In bfs0(Γmh−1), replace the 0-vertex by mh−1. Step 2. (Properties (ii) and (iii) ) Descend the vertex mh−1 and the right part of bfs0(Γmh−1) by a unit and introduce the new 0-vertex. Step 3. (Property (iv) ) Reproduce the left part of bfs0(Γmh−1) with the substitution 0 := mh−1. Step 4. (Property (v) ) Let r = 2. Introduce the vertex r(mh−1) as a child of vertex (r−1)(mh−1) and reproduce the genealogy of vertex (r − 1)(mh−1) with the substitution (r − 1)(mh−1) := r(mh−1). Step 5. (Property (v) ) Repeat Step 4 for r = 3, 4, . . . , m−1 2 Step 6. Complete bfs0(Γmh) using property (i). Remark 9. The method just presented is an extension of a method presented in [3] for constructing bfs0(Γ3h). Example 1. We illustrate the method by constructing a bfs tree rooted at 0-vertex for the graph Γ52 using bfs0(Γ51) in Figure 1 as an input. Using the propose method, we have a bfs tree rooted at 0-vertex for Γ52 as shown in Figure 3. J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 255 Figure 3: A bfs tree of the graph Γ52 with root 0. The green-colored vertices refer to the vertices that originally appeared in bfs0(Γ51). While the green-colored vertices with red edges refer to the descended vertices in bfs0(Γ51). The yellow-colored vertices refer to the resulting vertices as a result of reproducing the left part of bfs0(Γ51) with the substitution 0 := 5. The violet-colored vertices refer to the resulting vertices as a result of introducing the vertex 5 + 5 as a child of vertex 5 and reproducing the genealogy of vertex 5 with the substitution 5 =: 5 + 5. Finally, the blue-colored vertices are the vertices obtained using property (i). Example 2. In this example, we illustrate the method by constructing a bfs tree for the graph Γ72 with root 0 using bfs0(Γ71) shown in Figure 4 as an input. Using the propose method, we have a bfs tree for Γ72 with root 0 as shown in Figure 5. Figure 4: The bfs tree of Γ71 with 0-vertex as the root. Based on the bfs tree construction for Γmh with 0 as the root vertex, we have Theorem 1. Let h be a positive integer. Then dΓ mh (0, j) = { dΓ mh−1 (0, j) if j = 0, 1, 2, . . . , m h−1−1 2 dΓ mh−1 (0, j) + 1 if j =, m h−1−1 2 + 1 . . . ,mh−1 − 1. (1) Moreover, if kj , lij+ , and lij− ∈ V (Γmh) such that kj = mh−1 + j, lij+ = (i+ 1)(mh−1) + j and lij− = (i+ 1)(mh−1)− j where i = 1, 2, . . . , m−1 2 − 1 and j = 0, 1, . . . , m h−1−1 2 then dΓ mh (0, kj) = dΓ mh−1 (0, j) + 1, (2) and dΓ mh (0, lij+) = dΓ mh (0, lij−) = dΓ mh−1 (0, j) + (i+ 1) (3) J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 256 Figure 5: A bfs tree of the graph Γ72 . The green-colored vertices refer to the vertices that originally appeared in bfs0(Γ71). While the green-colored vertices with red edges refer to the descended vertices in bfs0(Γ71). The yellow-colored vertices refer to the resulting vertices as a result of reproducing the left part of bfs0(Γ71) with the substitution 0 := 7. The violet-colored vertices refer to the resulting vertices as a result of introducing the vertex 7 + 7 as a child of vertex 7 and reproducing the genealogy of vertex 7 with the substitution 7 =: 7 + 7. The beige-colored vertices refer to the resulting vertices as a result of introducing the vertex 7 + 7 + 7 as a child of vertex 7 + 7 and reproducing the genealogy of vertex 7 + 7 with the substitution 7 + 7 =: 7 + 7 + 7. The blue-colored vertices are the vertices obtained using property (i). Proof. Steps 1 and 2 imply that if j = mh−1, then dΓ mh (0, j) = 1 = dΓ mh−1 (0, 0) + 1. And that dΓ mh (0, j) = { dΓ mh−1 (0, j) if j ∈ L[bfs0(Γmh−1)] dΓ mh−1 (0, j) + 1 if j ∈ R[bfs0(Γmh−1)]. By referring to Remark 8 we verified equation (1). Next, we consider the implication of Step 3. Step 3 implies that if kj = mh−1 + j where j = 1, 2, . . . , m h−1−1 2 , we have dΓ mh (0, kj) = dΓ mh−1 (0, j) + 1. Combining this with the fact that for j = mh−1, we have dΓ mh (0, j) = 1 = dΓ mh−1 (0, 0) + 1 proves equation (2). The substitution part of Step 4 implies that for i = 1 and j = 0, we have dΓ mh (0, lij) = dΓ mh (0, l0j) + 1 where l0j = mh−1. While the part involving reproduction of genealogy implies that for i = 1 and j = 1, 2, . . . , m h−1−1 2 we have dΓ mh (0, lij+) = dΓ mh (0, lij−) = dΓ mh (0, kj) + 1. Using equation (2) we get dΓ mh (0, lij+) = dΓ mh (0, lij−) = dΓ mh−1 (0, j) + 1 + 1. This proves the i = 1 case of equation (3). Finally, Step 5 implies the validity of equation (3) for i = 2, 3, . . . , m−1 2 − 1. This completes the proof of the theorem. Example 3. Using the constructed bfs tree for Γ72 in Figure 5 we have {0, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 6, 6, 5, 4, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1} as the first row entries of D(Γ72). Using Theorem 1, given the first row of the distance matrix of the graph Γ72, we can determine the first row of the distance matrix of the graph Γ73. The first row of the distance matrix of the graph Γ73 is given by J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 257 {0, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 6, 7, 8, 7, 6, 5, 6, 7, 8, 7, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 6, 7, 8, 7, 6, 5, 6, 7, 8, 9, 8, 7, 6, 7, 8, 9, 8, 7, 6, 5, 6, 7, 8, 7, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 6, 7, 8, 7, 6, 5, 6, 7, 8, 9, 8, 7, 6, 7, 8, 9, 9, 8, 7, 6, 7, 8, 9, 8, 7, 6, 5, 6, 7, 8, 7, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 6, 7, 8, 7, 6, 5, 6, 7, 8, 9, 8, 7, 6, 7, 8, 9, 8, 7, 6, 5, 6, 7, 8, 7, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 6, 7, 8, 7, 6, 5, 6, 7, 8, 7, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 6, 7, 6, 5, 4, 3, 4, 5, 6, 5, 4, 3, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1} In the above set, we use six colors to represent the distances of each vertices per group. We use color green for the group of vertices covered by the first part of equation (1) while red for the group of vertices covered by second part. Color yellow were used for the group of vertices covered by equation (2), color violet were used for the group of vertices covered by equation (3) in the first implementation while color orange were used for the group of vertices covered by equation (3) in the second/final implementation. Finally, we used color blue for the group of vertices covered by property (i). Remark 10. The first row of the distance matrix of Γ72 and Γ73 are verified to be correct using Wolfram Mathematica [7] with the inputs d = GraphDistanceMatrix[CirculantGraph[49, {1,7}]]; d[[1]] and d = GraphDistanceMatrix[CirculantGraph[343, {1,7,49}]]; d[[1]]. Once the distance of all the vertices in V (Γmh) from the 0-vertex is known, the distance matrix of Γmh can be easily determined using Remark 1. In the next section, we discuss some of the many graph properties of Γmh that can be determined using its distance matrix. 4. Some consequences of the bfs tree construction for Γmh In this section, we use our proposed construction to reprove some known results involv- ing the diameter, average distance and distance spectral radius of Γmh . We also determine the following graph-related properties for Γmh : Wiener index, vertex-forwarding index, and bounds for its edge-forwarding index. Except for the diameter and average distance, the results in this section is a generalization of the results presented in [3] for Γ3h . J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 258 On the diameter, average distance and distance spectral radius of Γmh In 1974, Wong and Coppersmith [15] introduced a combinatorial problem related to multimodule memory organizations which involves “memory circulator”, a bank of inter- connected registers and control circuitry. One model of a memory circulator that was considered in [15] is actually the graph Γmh . They determined its diameter as well as its average distance by calculating the points (with integral coordinate) which can be reached from 0 in a given number of steps displayed in the Cartesian coordinate plane showing a uniform filled pattern. Wong and Coppersmith found out that the diameter of Γmh for odd base m is given by h ( m−1 2 ) . They also found out that the average distance of Γmh where the “average distance” refers to the sum of all entries in D (Γmh) divided by the number of entries is given by h m ( m2−1 4 ) . As a consequence, since the distance matrix of Γmh is circulant, the distance spectral radius of Γmh is then given by ( m2−1 4 ) h(mh−1). We reprove the results involving Γmh ’s diameter and distance spectral radius using our proposed bfs tree construction in this subsection. This subsection is motivated by the work of Liu et al. [9] where they determined the distance spectral radius of certain class of circulant graphs. To determine the diameter of Γmh , we begin by proving a relationship between the diameters of Γmh and Γmh−1 . Theorem 2. The two diameters diam(Γmh) and diam(Γmh−1) are related by diam(Γmh) = diam(Γmh−1) + m− 1 2 . (4) Proof. We start by initially assuming that diam(Γmh)=diam(Γmh−1). Performing the steps necessary to construct bfs0(Γmh) from bfs0(Γmh−1) gives the following update in the initial diameter of Γmh Step 1: diam(Γmh)=diam(Γmh−1) Step 2: diam(Γmh)=diam(Γmh−1) + 1 Step 3: diam(Γmh)=diam(Γmh−1) + 1 Step 4: diam(Γmh)=diam(Γmh−1) + 1 + 1 Step 5: diam(Γmh)=diam(Γmh−1) + 1 + 1 + 1 + 1 + . . .+ 1︸ ︷︷ ︸ m−1 2 − 2 . Step 6: diam(Γmh)=diam(Γmh−1) + 1 + 1 + 1 + 1 + . . .+ 1︸ ︷︷ ︸ m−1 2 − 2 . Hence diam(Γmh) = diam(Γmh−1) + m−1 2 . Corollary 1. The diameter of Γmh is h ( m−1 2 ) . J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 259 Proof. Note that for all odd integer m > 1, we have diam(Γm1) = m−1 2 . Using Theorem 2, we have diam(Γm2) = diam(Γm1) + (m− 1) 2 = 2 ( m− 1 2 ) . diam(Γm3) = diam(Γm2) + (m− 1) 2 = 3 ( m− 1 2 ) . ... diam(Γmh) = diam(Γmh−1) + (m− 1) 2 = (h− 1) ( m− 1 2 ) + (m− 1) 2 . = h ( m− 1 2 ) . The next result gives the relationship between the two distance spectral radii ρ(Γmh) and ρ(Γmh−1). Theorem 3. The two distance spectral radii ρ(Γmh) and ρ(Γmh−1) are related by ρ(Γmh) = mρ(Γmh−1) + (m− 1)(m+ 1) 2 mh−1. (5) Proof. Note that the distance spectral radius of Γmh corresponds to the sum of all distances in bfs0(Γmh). Initially, we have ρ(Γmh) = ρ(Γmh−1). As we go over the steps of constructing bfs0(Γmh) from bfs0(Γmh−1), the value of ρ(Γmh) will be updated. After performing Step 2, the initial value of ρ(Γmh) will be added by the number of distance created as a result of descending the vertices mh−1 and the right part of bfs0(Γmh−1) by a unit. The number of created distance of the just stated action is exacty |R[bfs0(Γmh−1)]|+ 1. So we have ρ(Γmh) = ρ(Γmh−1) + |R[bfs0(Γmh−1)]|+ 1 after Step 2. For Step 3, reproducing the left part of bfs0(Γmh−1) will create a distance of ρ(Γ mh−1 ) 2 . Since the reproduction starts at vertex mh−1 which is of distance 1 to the 0−vertex, we need to add another |L[bfs0(Γmh−1)]|. So, after Step 3, we have ρ(Γmh) = ρ(Γmh−1) + |R[bfs0(Γmh−1)]|+ 1 + ρ(Γ mh−1 ) 2 + |L[bfs0(Γmh−1)]|. J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 260 The action reproduce the genealogy ofmh−1 in Step 4 will create a distance of ρ(Γmh−1). Moreover, since the reproduction starts at vertex 2mh−1 which is of distance 2 to the 0−vertex, we need to add another 2(mh−1). As a result, we have ρ(Γmh) = ρ(Γmh−1) + |R[bfs0(Γmh−1)]|+ 1 + ρ(Γ mh−1 ) 2 + |L[bfs0(Γmh−1)]|+ ρ(Γmh−1) + 2(mh−1). The principle that holds in Step 4 is the same principle that holds for Step 5. In general, for r ∈ {3, 4, . . . , m−1 2 } we have an additional distance ρ(Γmh−1) + r(mh−1). So after Step 5, we have ρ(Γmh) = ρ(Γmh−1) + |R[bfs0(Γmh−1)]|+ 1 + ρ(Γmh−1) 2 + |L[bfs0(Γmh−1)]| + m−1 2∑ r=2 [ ρ(Γmh−1) + r(mh−1) ] = ρ(Γmh−1) + ρ(Γmh−1) 2 +mh−1 + ( m− 1 2 − 1 ) ρ(Γmh−1) + m−1 2∑ r=2 r(mh−1) = ( 1 + 1 2 + m− 1 2 − 1 ) ρ(Γmh−1) + m−1 2∑ r=1 r(mh−1) = m 2 ρ(Γmh−1) + (m− 1)(m+ 1) 4 (mh−1). Finally, performing Step 6 doubles the current value of ρ(Γmh). As a result, we have the final value of ρ(Γmh) = 2 [ m 2 ρ(Γmh−1) + (m− 1)(m+ 1) 4 (mh−1) ] = mρ(Γmh−1) + (m− 1)(m+ 1) 2 mh−1. An explicit formula for the distance spectral radius of the graph Γmh for any positive integer h is given in the next result. Corollary 2. For all positive integer h, we have ρ(Γmh) = ( m2 − 1 4 ) h(mh−1). Proof. For h = 1, we have ρ(Γm1) = m−1 2∑ i=1 2i = ( m2 − 1 4 ) (1)(m1−1). Now, let h > 1 be an integer and suppose that for all k < h we have ρ(Γmk) = ( m2−1 4 ) k(mk−1). We show that for h we have ρ(Γmh) = ( m2−1 4 ) h(mh−1). J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 261 By Theorem 3 we have ρ(Γmh) = mρ(Γmh−1) + (m− 1)(m+ 1) 2 mh−1. Now since h− 1 < h, using our induction hypothesis yields ρ(Γmh) = m [( m2 − 1 4 ) (h− 1)(mh−2) ] + ( m2 − 1 2 ) mh−1 = ( m2 − 1 4 ) (h− 1)(mh−1) + ( m2 − 1 2 ) mh−1 = ( m2 − 1 4 ) (h− 1 + 1)(mh−1) = ( m2 − 1 4 ) h(mh−1). Remark 11. For h = 1, 2, . . ., the sequence ( m2−1 4 ) h(mh−1) denotes the distance spectral radius of Γmh. For m = 3, the sequence generated is the sequence A212697 [13] in The On-line Encyclopedia of Integer Sequence (OEIS). For m = 5, the sequence generated is the sequence A269760 [6] in the OEIS. The Wiener Index and Average Distance of Γmh This subsection is motivated by the works of Ali et al. [1, 2], where they determined some distance-based topological indices for certain class of circulant graphs. The com- putation of the Wiener index of the graph Γmh follows immediately from Corollary 2, Remark 4, and Remark 1. Theorem 4. The Wiener index of Γmh is h 8 (m2h−1)(m2 − 1). The next result about the average distance of MC(mh) follows immediately from Theorem 4 and Remark 5. Theorem 5. The average distance of Γmh is h 4 (m2−1)(mh−1) mh−1 . Exact Value of Γ′ mhs Vertex-Forwarding Index This subsection and the last is motivated by the work of Liu et al. [9] where they determined the exact values of vertex-forwarding index and bounds for the edge-forwarding index of some class of circulant graphs. The exact value of the vertex-forwarding index of Γmh is given in the next result. J. Antalan, F. Campeña / Eur. J. Pure Appl. Math, 14 (1) (2021), 248-264 262 Theorem 6. Let m > 1 be odd and h be a positive integer. Then ξ(Γmh) = ( m2 − 1 4 ) h(mh−1)− (mh − 1). Proof. Follows from Theorem 2 and Lemma 2. Bounds for MC(mh)′s Edge-Forwarding Index Our final result in this section gives an upper and lower bounds for Γ′ mhs edge- forwarding index. The result follows from Theorem 2, Lemma 3 and the fact that Γmh is a 2h-regular graph. Theorem 7. Let m > 1 be odd and h be a positive integer. Then( m2 − 1 4 ) (mh−1) ≤ π(Γmh) ≤ mh−1 ( m+ m2 − 1 4 h ) − 4h+ 1. 5. Future applications of the bfs tree construction for Γmh In this short section, we state some particular research works in which the proposed bfs tree construction can be applied. As stated earlier, Ali et al. [1, 2]computed some distance-based topological indices for some class of circulant graphs. In particular, they determined the Wiener index, hyper-Wiener index, and Schultz molecular topological index of circulant graph class Cay(Zn, {1, a}) where a = 2, 3, 4, 5. Since the proposed construction presented in this paper determines the distance of 0-vertex to all the other vertices of the graph Γmh , and the distance matrix of Γmh is circulant, we can use the proposed construction to obtain Γmh ’s distance matrix. Once the distance matrix of Γmh is known, the computation for some distance-based topological indices can be performed. The distance matrix of Γmh can also be used to aid in the study of various distance- based coloring problem related to multiplicative circulant graphs. For instance, the L(h, k)-coloring problem. 6. Conclusion In this paper, we successfully presented a method in constructing a breadth-first search tree for multiplicative circulant graphs of order power of odd with 0-vertex as the root. As a consequence, we were able to reprove some known results about multiplicative circulant graph’s diameter, average distance, and distance spectral radius. We also determined the Wiener index, vertex-forwarding index, and bounds for the edge-forwarding index of the studied multiplicative circulant graph. New integer sequences were also generated. Finally, we stated some particular research works in which the proposed bfs tree construction can be applied. REFERENCES 263 In our next paper, we wish to determine some distance-based topological indices for multiplicative circulant graphs that utilizes our bfs tree construction. Acknowledgements The creation of this paper and the research behind it would not have been possible without the support of the Philippines’ Department of Science and Technology ASTHRDP- NSC, Central Luzon State University, and De La Salle University. The authors are also thankful to the referees for their valuable comments and suggestions that helped improve the content of this paper. References [1] F. Ali, A. Hafeez, M. Salman, and S. Huang. On computation of some distance- based topological indices of circulant networks. Hacettepe Journal of Mathematics and Statistics, 47:1427–1437, 2018. [2] F. Ali, A. Hafeez, M. Salman, and S. Huang. On computation of some distance-based topological indices of circulant networks-II. Journal of Information and Optimization Sciences, 39:759–782, 2018. [3] J.R.M. Antalan and F.J.H. Campena. Distance eigenvalues and forwarding indices of multiplicative circulant graph of order power of two and three. arXiv e-prints, arXiv:2009.11608, arXiv:2009.11608[math.CO], (Submitted to Electronic Journal of Graph Theory and Applications, September 25, 2020), 2020. [4] J.-C. Bermond, F. Comellas, and D.-F. Hsu. Distributed loop computer networks: A survey. Journal of Parallel and Distributed Computing, 24:2–10, 1995. [5] J.L. Gross, J. Yellen, and P. Zhang. Handbook of Graph Theory Second Edition. CRC Press, Taylor and Francis Group, Boca Raton, FL, 2014. [6] R.H. Hardin. Sequence A269760 in the On-line Encyclopedia of Integer Sequences., 2016. [7] Wolfram Research, Inc. Mathematica, Version 9.0.1. Champaign, IL, 2020. [8] F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kauffman Publishers, 1992. [9] S. Liu, H. Lin, and J. Shu. Distance eigenvalues and forwarding indices of circulants. Taiwanese Journal of Mathematics, 22:513–528, 2018. [10] B. Mans. Optimal distributed algorithms in unlabeled tori and chordal rings. Journal of Parallel and Distributed Computing, 46:80–90, 1997. REFERENCES 264 [11] J-H. Park and K-Y. Chwa. Recursive circulant: A new topology for multicomputer networks. In Proceedings of International Symposium on Parallel Architectures, Al- gorithms and Networks., pages 73–80, 1994. [12] I. Stojmenovic. Multiplicative circulant networks: Topological properties and com- munication algorithms. Discrete Applied Mathematics, 77:281–305, 1997. [13] S. Sykora. Sequence A212697 in the On-line Encyclopedia of Integer Sequences., 2012. [14] S-M. Tang, Y-L. Wang, and C-Y. Li. Generalized recursive circulant graphs. IEEE Transactions on Parallel Distributed Systems, 23:87–93, 2012. [15] C.K. Wong and D. Coppersmith. A combinatorial problem related to multimodule memory organizations. Journal of the Association for Computing Machinery, 21:392– 402, 1974.