J Supercomput (2011) 56: 212–225 DOI 10.1007/s11227-009-0363-9

Optimal Independent Spanning Trees on Odd Graphs Jong-Seok Kim · Hyeong-Ok Lee · Eddie Cheng · László Lipták

Published online: 25 November 2009 © Springer Science+Business Media, LLC 2009

Abstract The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of faulttolerance and bandwidth. The designs of multiple ISTs on several classes of networks have been widely investigated. In this paper we show a construction algorithm of ISTs on odd graphs, and we analyze that all the lengths of the paths in the ISTs are less than or equal to the length of the shortest path + 4, which is optimal. We also prove that the heights of the ISTs we constructed are d + 1, which again is optimal, since the fault diameter of an odd graph is d + 1. Keywords Optimal independent spanning trees · Odd graphs · Internally disjoint paths · Algorithms 1 Introduction Graph theory has provided powerful mathematical tools for designing interconnection networks, where vertices represent processing elements and edges correspond to communication links. The performance of a particular parallel computer is heavily dependent on the graph topology chosen for it. Many graph topologies have been proposed in literature, ranging from simple graphs such as trees to more sophisticated J.-S. Kim School of Electrical Engineering and Computer Science, Yeungnam University, Gyeongsan, Gyeongbuk 712-749, Korea H.-O. Lee () Department of Computer Education, Sunchon National University, Sunchon, Chonnam 540-742, Korea e-mail: [email protected] E. Cheng · L. Lipták Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA

Optimal Independent Spanning Trees on Odd Graphs

213

graphs such as tori, hypercubes, star graphs and odd graphs. They possess various degrees and diameters. These graphical parameters are not only important in graph theory and combinatorics but also relevant to applications in commercial networks. The graph model having a smaller degree and diameter is considered more desirable because this implies a lower hardware implementation cost and shorter transmission time of messages [20]. One of the central problems in interconnection networks research is to design network topologies that have good properties. These properties can be grouped into two major categories: better performance and lower cost. Cost usually refers to the number of the links, and performance usually refers to fault-tolerance, broadcast time, or ease of routing schemes. The best performance can be achieved when all vertices of a graph are connected to all the rest, i.e., in a complete graph. But this is practically impossible and very costly. A compromise between cost and performance should be done and this is the reason behind the research to design networks with good structural characteristics as well as near optimal performance. The study of independent spanning trees has applications in fault-tolerant protocols for distributed computing networks. For example, broadcasting in a network is sending a message from a given vertex to all the other vertices in the network. A faulttolerant broadcasting protocol can be designed by means of independent spanning trees [1, 11]. The vertex set and the edge set of a graph G are denoted by V (G) and E(G), respectively. Two paths, P and Q, connecting a vertex v to a vertex w are said to be internally disjoint if E(P ) ∩ E(Q) = ∅ and V (P ) ∩ V (Q) = {v, w}. A spanning tree of a graph G is a subgraph of G that contains all vertices in G and forms a tree. Two rooted spanning trees, T and T  , of a graph G are said to be independent (referred to as ISTs for short) if they are rooted at the same vertex, say r, and for each vertex v = r, the two paths from r to v, one path in each tree, are internally disjoint (or called vertex-disjoint). Also, we call a set of rooted spanning trees of G to be independent if they are pairwise independent. Recently, the problem of constructing multiple ISTs of a given graph has received much attention. In fact, Zehavi and Itai [27] conjectured that for any k-connected graph G and each vertex r of G, there exist k ISTs of G rooted at r. The conjecture has been confirmed only for k-connected graphs with k ≤ 4 in [3, 4, 11, 27], and it is still open for arbitrary k-connected graphs when k ≥ 5. Moreover, by providing the construction schemes of ISTs, the conjecture has been proved to hold for several restricted classes of graphs or digraphs, such as planar graphs [9, 10, 17, 18], product graphs [19], chordal rings [12, 24], de Bruijn and Kautz digraphs [5, 7], multidimensional torus [22], locally twisted cubes [8], recursive circulant graphs [25, 26], hypercubes [21, 23], etc. The class of odd graphs was introduced by [2, 16] in the context of graph theory. However, [6] pointed out their potential as fault-tolerant interconnection networks and their efficient properties such as routing, diagnosability, combinatorial structure, maximal fault-tolerance [6], symmetry [2], fault diameter [6, 13], embedding [15], broadcasting [14], Hamiltonian cycle [16] were analyzed. Odd graphs are competitive with mesh and hypercube variants. For the same number of vertices, the network cost (degree × diameter) of odd graph is superior to the comparable mesh and hypercube variants.

214

J.-S. Kim et al.

In this paper, we study the problem of constructing multiple ISTs on odd graphs. The rest of this paper is organized as follows. In Sect. 2 we summarize the notations and definitions that will be used throughout the paper. In Sect. 3 we show our algorithm to construct multiple ISTs on Od . The final section contains the conclusion.

2 Preliminaries A binary string x of length n will be written as x1 x2 . . . xi . . . xn , where xi ∈ {0, 1}, 1 ≤ i ≤ n. xi is called the ith bit, and the complement of xi will be denoted by x¯i = 1 − xi . Let s and t be two binary strings. The Hamming distance Hst between the binary strings s and t is the number of bits that they differ. The vertex set of the odd graph Od with d ≥ 2 is the set of binary strings of length 2d − 1 with exactly d 1’s. Two vertices of Od are adjacent if and only if their Hamming dis, the degree of every vertex tance is 2d − 2. The number of vertices in Od is 2d−1 d is d, and the diameter of Od is d − 1. When there is an edge connecting two vertices u and v, they must differ in all but one position. Call this edge an i-edge if u and v agree on the ith bit, and let σi (u) denote the vertex obtained from u by changing all but the ith bit. In other words, two vertices u = u1 u2 . . . ui . . . u2d−1 and v = v1 v2 . . . vi . . . v2d−1 are connected when v = σi (u) for some i = 1, 2, . . . , n. For a vertex u, we denote by [k1 , k2 , . . . , kt ] the path formed by the vertices obtained by applying σk1 , σk2 , . . . , σkt successively to u. Clearly every path can be represented in such a way, though not every sequence represents a path. For example, for u = 0001111, [4, 1, 5] represents the path 0001111–1111000–1000111–0111100, while [5, 1, 4] represents 0001111–1110100–1001011–0111100 in O4 . Notice that if k1 , k2 , . . . , kt are all different, and [k1 , k2 , . . . , kt ] is a path from u to v, then we can permute the ki ’s with even indices and we can permute the ki ’s with odd indices and still get path from u to v of the same length (other permutations do not correspond to paths). Thus the same applies to shortest paths. We will use 0d−1 1d to denote the d−1

d

      vertex 0 . . . 0 1 . . . 1 in Od . Let dist(u, v) be the distance from u = u1 u2 . . . u2d−1 to v = v1 v2 . . . v2d−1 in Od . It was proven in [6] that dist(u, v) = min{Huv , Huv¯ }. Let r be the bitstring obtained by applying the bitwise Exclusive-OR (denoted by ⊕) operation to u and v, so r = r1 r2 . . . r2d−1 , where ri = ui ⊕ vi . Assuming that a shortest path to connect the two vertices u and v is P , and P is the path represented by [k1 , k2 , . . . , kt ], the set {k1 , k2 , . . . , kt } is either S = {i|ri = 1, 1 ≤ i ≤ 2d − 1} or S  = {i|ri = 0, 1 ≤ i ≤ 2d − 1}. If the distance between u and v is Huv , then the set of elements included in P is S, and if the distance is Huv¯ , the set is S  . A layered graph consists of vertices in t + 1 layers, which are numbered L0 to Lt , such that each vertex is in one layer, and each edge connects vertices in consecutive layers. Many multiprocessor networks can be represented as layered graphs. One of the examples is the hypercube. The odd graph Od can be represented in a form similar to layered graph, although it is not layered graph. In this paper, the odd graph, shown in a similar form to a layered graph, is called a quasi-layered graph. The odd graph Od is represented as a quasi-layered graph as follows: A vertex u is chosen to be in layer L0 , and for every other vertex v, if dist(u, v) = m, then vertex v is put

Optimal Independent Spanning Trees on Odd Graphs

215

Fig. 1 O4

in layer Lm . Then Od has layers from L0 to Ld−1 , and every edge either connects vertices in consecutive layers or two vertices of Ld−1 . Figure 1 shows O4 as a quasilayered graph with u = 0001111. The following lemmas describe even and odd cycles in Od . Lemma 1 [6] Let k1 , k2 , . . . , kρ be distinct integers with 3 ≤ ρ ≤ 2d − 2. If starting from u, P = [k1 , k2 , . . . , k2ρ ] represents a walk in Od , d ≥ 3, and kρ+1 , kρ+2 , . . . , k2ρ is a cyclic permutation of k1 , k2 , . . . , kρ , then P is an even cycle in Od . Lemma 2 [2] The minimum length of an odd cycle in Od , d ≥ 3, is 2d − 1. Lemma 1 can be easily generalized as follows: Lemma 3 Let k1 , k2 , . . . , kρ be distinct integers with 3 ≤ ρ ≤ 2d − 2. Assume that starting from vertex u, P = [k1 , k2 , . . . , k2ρ ] represents a walk in Od , d ≥ 3, and kρ+1 , kρ+2 , . . . , k2ρ is a permutation of k1 , k2 , . . . , kρ . If no proper subsequence of P of even length has the property that the second half of it is a permutation of the first half, then P is an even cycle in Od .

3 Constructing independent spanning trees on Od We fix u = 0d−1 1d , and let v = b1 b2 . . . bi . . . b2d−1 be a vertex of the odd graph Od . Let the result of applying the bitwise Exclusive-OR function on these two vertices be the bitstring r = r1 r2 . . . ri . . . r2d−1 (ri = ui ⊕ bi ). The set R 1 , consisting of bit positions i such that ri = 1, is divided into the following two sequences: bit positions

216

J.-S. Kim et al.

up to d − 1 are put in H1 , bit positions that are at least d are put into H2 , both in an increasing order. Thus if R 1 = {i1 , i2 , . . . , it } such that i1 < i2 < · · · < ig ≤ d − 1 < ig+1 < · · · < it , then H1 = i1 , i2 , . . . , ig  and H2 = ig+1 , ig+2 , . . . , it . It is easy to see that in this case t is even and g = 2t . The set R 0 , consisting of bit positions i such that ri = 0, is divided into the two sequences H3 and H4 the same way, thus if R 0 = {i1 , i2 , . . . , it } such that i1 < i2 < · · · < if ≤ d − 1 < if +1 < · · · < it , then H3 = i1 , i2 , . . . , if  and H4 = if +1 , if +2 , . . . , it . Again, it is easy to see that t is an odd and f = t−1 2 . Later in the construction we will need to refer to exactly one of R 1 and R 0 , and t will mean the corresponding value. LRx (S) will denote the sequence obtained from the sequence S by rotating its elements left x times. For example, if S = 1, 2, . . . , n, then LR0 (S) = 1, 2, . . . , n, and LR3 (S) = 4, 5, . . . , n, 1, 2, 3. In this paper, od will represent an odd number, while ev will represent an even number. Assume that P is a path connecting two vertices u and v in the odd graph Od . From the numbers representing the path P , pick the ones in odd positions to form S1 = a1 , a2 , . . . , ap , and pick the ones in even positions to form S2 = b1 , b2 , . . . , bq . Given sequences S1 and S2 with p = q or p = q + 1, S1 ⊗ S2 will represent the new permutation obtained when we alternately pick elements of S1 and S2 (finishing with an element of S1 in case p = q + 1). For instance, if S1 = 5, 6, 7 and S2 = 2, 3, 4, then S1 ⊗ S2 = 5, 2, 6, 3, 7, 4. In this section, we construct d directed ISTs, rooted at vertex u = 0d−1 1d of Od . Since Od is vertex-symmetric [2], our result will imply that one can construct similar ISTs with any vertex as the root. The ISTs will be denoted by Tα (d ≤ α ≤ 2d − 1), and each IST includes all vertices of Od . In the IST Tα , let Paα (v) represent the parent vertex of v, and let Chα (v) represent the child vertex of v. The root vertex u will only have one child vertex Chα (u) in each IST, with Chα (u)(∈ L1 ) being connected to vertex u by an α-edge. To construct the spanning trees, we will specify the paths from each vertex v to the root. To specify the paths it will be sufficient to choose the parent of each vertex in Tα . Note that to get ISTs, each neighbor of v must appear in exactly one of the trees as a parent of v. The idea behind choosing the appropriate parent in Tα is the following: The shortest paths from v to u in Od are always permutations of either H1 ∪ H2 or H3 ∪ H4 , depending on which is smaller. For α’s in the smaller set we will just choose an appropriate permutation ending with an α-edge, and choose a parent to follow it. If α is in the larger set and an α-edge is incident to v in Od , we choose it to get the parent, then follow a shortest path to u ending with an α-edge. Finally, if α is in the larger set and no α-edge is incident to v in Od , we choose a parent using an i from H1 , then choose an α-edge, then follow a shortest path to u ending with an α-edge. We now describe an algorithm, denoted by Parent(v, Tα ), to compute Paα (v) for a given vertex v = u. Clearly α ∈ H2 or α ∈ H4 . If α ∈ H2 , thus H2 =

ig+1 , ig+2 , . . . , ig+c (= α), . . . , it , we apply x = c − 1 left rotations to move α to the first position, getting the sequence LRx (H2 ) = sg+1 , sg+2 , . . . , st  with sg+1 = ig+c = α. Similarly, if α ∈ H4 , thus H4 = if +1 , if +2 , . . . , if +c (= α), . . . , it , we apply x = c − 1 left rotations to move α to the first position, getting the sequence LRx (H4 ) = sf +1 , sf +2 , . . . , st  with sf +1 = if +c = α. Thus for every v = u we obtain a sequence, either LRx (H2 ) or LRx (H4 ), with α in the first position (so t will correspond to the sequence containing α). These rotations will allow us to choose

Optimal Independent Spanning Trees on Odd Graphs

217

different parents for v for the different α’s. Depending on the location of v and α, we apply one of the following six cases: Case 1 α ∈ H2 and v ∈ Lev : If LRx (H1 ) = s1 , s2 , . . . , sg , then LRx (H2 ) ⊗ LRx (H1 ) = sg+1 , s1 , sg+2 , s2 , . . . , st , sg , so define Paα (v) to be σsg (v). For example, let the two vertices of O4 be u = 0001111 and v = 1000111, and α = 4. Then ev = t = 2, R 1 = {1, 4}, H1 = 1, H2 = 4, and x = 0, which implies LR0 (H2 ) = 4, LR0 (H1 ) = 1, and LR0 (H2 )⊗LR0 (H1 ) = 4, 1, thus consequently, Pa4 (1000111) = σ1 (1000111) = 1111000. Case 2 α ∈ H4 and v ∈ Lod : If LRx (H3 ) = s1 , s2 , . . . , sf , then LRx (H4 ) ⊗ LRx (H3 ) = sf +1 , s1 , sf +2 , s2 , . . . , sf , st , so define Paα (v) to be σst (v). For example, let the two vertices of O4 be u = 0001111 and v = 0111100, and α = 4. Then od = t = 3, R 0 = {1, 4, 5}, H3 = 1, H4 = 4, 5, and x = 0, which implies LR0 (H4 ) = 4, 5, LR0 (H3 ) = 1, and LR0 (H4 ) ⊗ LR0 (H3 ) = 4, 1, 5, thus consequently, Pa4 (0111100) = σ5 (0111100) = 1000111. Case 3 α ∈ H4 and v ∈ Lev and ev = d − 1: If LRx (H3 ) = s1 , s2 , . . . , sf , then LRx (H4 ) ⊗ LRx (H3 ) = sf +1 , s1 , sf +2 , s2 , . . . , sf , st , so define Paα (v) to be σst (v). For example, let the two vertices of O3 be u = 00111 and v = 01101, and α = 3. Then ev = 2, t = 3, R 0 = {1, 3, 5}, H3 = 1, H4 = 3, 5, and x = 0, which implies LR0 (H4 ) = 3, 5, LR0 (H3 ) = 1, and LR0 (H4 ) ⊗ LR0 (H3 ) = 3, 1, 5, thus consequently, Pa3 (01101) = σ5 (01101) = 10011. Case 4 α ∈ H2 and v ∈ Lod and od = d − 1 or od = d − 2: If LRx (H1 ) =

s1 , s2 , . . . , sg , then LRx (H2 ) ⊗ LRx (H1 ) = sg+1 , s1 , sg+2 , s2 , . . . , st , sg , so define Paα (v) to be σsg (v). For example, let the two vertices of O4 be u = 0001111 and v = 0110110, and α = 4. Then od = 3, t = 4, R 1 = {2, 3, 4, 7}, H1 = 2, 3, H2 = 4, 7, and x = 0, which implies LR0 (H2 ) = 4, 7, LR0 (H1 ) = 2, 3, and LR0 (H2 ) ⊗ LR0 (H1 ) =

4, 2, 7, 3, thus consequently, Pa4 (0110110) = σ3 (0110110) = 1011001. Similarly, if the two vertices of O3 are u = 00111 and v = 11010, and α = 3, then od = 1, t = 4, R 1 = {1, 2, 3, 5}, H1 = 1, 2, H2 = 3, 5, and x = 0, which implies LR0 (H2 ) =

3, 5, LR0 (H1 ) = 1, 2, and LR0 (H2 ) ⊗ LR0 (H1 ) = 3, 1, 5, 2, thus consequently, Pa3 (11010) = σ2 (11010) = 01101. Case 5 α ∈ H4 and v ∈ Lev and ev ≤ d − 2: Define Paα (v) to be σα (v). For example, let the two vertices of O4 be u = 0001111 and v = 1001011, and α = 4. Then ev = 2, and Pa4 (1001011) = σ4 (1001011) = 0111100. Case 6 α ∈ H2 and v ∈ Lod and od < d − 2 (thus t > d): If LRx (H1 ) = s1 , s2 , . . . , sg , then define Paα (v) to be σs1 (v). For example, let the two vertices of O4 be u = 0001111 and v = 1110100, and α = 4. Then t = 6, R 1 = {1, 2, 3, 4, 6, 7}, H1 = 1, 2, 3, H2 = 4, 6, 7, thus Pa4 (1110100) = σ1 (1110100) = 1001011.

218 Table 1 Summary of the cases in Parent(v, Tα )

J.-S. Kim et al. Case

α∈

Level of v in Od

Paα (v) is given by

1

H2

ev = |H1 ∪ H2 |

Last element of LRx (H1 )

2

H4

od = |H3 ∪ H4 |

Last element of LRx (H4 )

3

H4

ev = |H1 ∪ H2 | = d − 1

Last element of LRx (H4 )

4

H2

od = |H3 ∪ H4 | ≥ d − 2

Last element of LRx (H1 )

5

H4

ev = |H1 ∪ H2 | ≤ d − 2

α

6

H2

od = |H3 ∪ H4 | < d − 2

First element of LRx (H1 )

Fig. 2 T4 of O4

These six cases are summarized in Table 1. It is easy to see that they cover all possibilities. Figures 2, 3, 4 and 5 show the ISTs of O4 . Lemma 4 The tree Tα with vertex u = 0d−1 1d as root vertex is a spanning tree of Od for d ≤ α ≤ 2d − 1. Proof Since Tα includes all vertices of Od , and in Cases 1–6 we defined one fewer edges, it is enough to show that it is connected, that is, there is a path from every vertex to u. This will follow from the claim that for any vertex v, if we repeatedly go to its parent given by Paα , eventually we get to vertex u. Note that when we apply σi , elements of H1 and H3 get switched and elements of H2 and H4 get switched, except for i, which stays in the set it originally was. Also, |H1 ∪ H2 | is always even and |H3 ∪ H4 | is always odd, and the level to which v belongs to is the smaller of them. For v-σi (v) to be an edge in Od , we must have i ∈ H1 ∪ H4 , too. Using these observations one can find which of the six cases Paα (v) will fall under, given where v fell.

Optimal Independent Spanning Trees on Odd Graphs

219

Fig. 3 T5 of O4

Fig. 4 T6 of O4

If v falls under Case 1, then Paα (v) ∈ Lev−1 , and α switches to H4 , so Paα (v) falls under Case 2. If v falls under Case 2, then Paα (v) ∈ Lod−1 , and α switches to H2 , unless st = α, in which case we must have t = 1, thus v = σα (v), so either Paα (v) falls under Case 1 or Paα (v) = u. If v falls under Case 3, then Paα (v) ∈ Lev , and α switches to H2 , so Paα (v) falls under Case 1 (this case can only occur if d is odd).

220

J.-S. Kim et al.

Fig. 5 T7 of O4

If v falls under Case 4, then α switches to H4 . If d is even, then od = d − 1 and Paα (v) ∈ Lod , so Paα (v) falls under Case 2. If d is odd, then od = d − 2 and Paα (v) ∈ Lod+1 , so Paα (v) falls under Case 3. If v falls under Case 5, then Paα (v) ∈ Lev+1 , and α stays in H4 , so Paα (v) falls under Case 2. If v falls under Case 6, then Paα (v) ∈ Lod+1 , and α switches to H4 , so Paα (v) falls under Case 5. From these cases we can see that after at most two iterations the vertex will fall under Cases 1 or 2, after which we only go up in level, so eventually we reach u. Since we make at most two moves (from Case 4 when d is odd, and from Case 6 when d is even) before we get to Case 1 or 2, the height of Tα is at most d + 1. Since there is always a vertex from which we make two such moves first and reach level d − 1, the height of Tα is always d + 1.  Theorem 1 The spanning trees Tα with vertex u = 0d−1 1d as the root vertex are optimal for d ≤ α ≤ 2d − 1. Proof Optimality of the trees Tα means that for any vertex v = u and any α, the path from v to u in Tα is a shortest path in Od from v to u among paths containing the edges v-Paα (v) and u-σα (u). Note that most of these paths are shortest among paths from u to v in Od containing the α-edge u-σα (u). However, some of them are not shortest under such conditions, as we will see later. Since our aim is to construct ISTs, each edge incident to v has to be used in exactly one of the trees, so optimality can be considered in the above sense. Let v = u be an arbitrary vertex in Od , let P be the path from vertex v to vertex u in Tα , and let Q denote a shortest path from vertex u to vertex v in Od . Let ψ represent the length of a shortest path from v to u in Qd containing the α-edge u-σα (u)

Optimal Independent Spanning Trees on Odd Graphs

221

and the edge v-Paα (v). We want to show that the length of P is ψ. Now to prove the optimality of path P in Tα we consider the cases in the definition of Paα (v): 1. Case 1 or 2 in Parent(v, Tα ): According to the algorithm Parent(v, Tα ), we always go up in level, so ψ = dist(u, v). This means that P has optimal length. 2. Case 3 or od = d − 1 in Case 4 in Parent(v, Tα ): Then dist(u, v) = d − 1, so the length of Q is d − 1, and either α ∈ H2 and v ∈ Lod or α ∈ H4 and v ∈ Lev . Since there is no α-edge on Q, ψ = dist(u, v), thus ψ ≥ dist(u, v) + 1 = d. According to the algorithm, applying Paα first moves to a vertex on the same level, then it falls under Case 1 or 2, after which we always move up one level, so the length of P is d, so it has optimal length. 3. Case 5 in Parent(v, Tα ): The first move goes to a lower level, so ψ ≥ dist(u, v)+2. The algorithm first makes a move down, after which it falls under Case 2, so the remaining moves always go up, so P also has length dist(u, v) + 2, so it is optimal. 4. od = d − 2 in Case 4 in Parent(v, Tα ): Then α ∈ H2 , v ∈ Lod , and dist(u, v) = d − 2, so the length of Q is d − 2. The first move goes down to level d − 1, so ψ ≥ d. There is no α-edge on Q, and the first move was not an α-edge either, so ψ = d. Since the algorithm then takes a move to a vertex on the same level, after which it only makes moves up, so the length of P is d + 1, so it has optimal length. Note, however, that if we only restrict the path from v to u to contain the α-edge u-σα (u), then the shortest such path has length d for d ≥ 5, since one can make a move up, then use an α-edge to move down, after which one can move all the way up to get a path of length d finishing with the α-edge u-σα (u). 5. Case 6 in Parent(v, Tα ): The first move goes down one level, so ψ ≥ dist(u, v) + 2. There is no α-edge on Q, and the first move was not an α-edge either, so ψ = dist(u, v) + 2. Since dist(u, v) ≤ d − 3, if we had ψ = dist(u, v) + 3, we would get an odd cycle of length 2d − 3, which is not possible by Lemma 2. Thus ψ ≥ dist(u, v) + 4, and since the algorithm first takes two moves down, then makes moves only up, P has optimal length. Again, note that if we only restrict the path from v to u to contain the α-edge u-σα (u), then the shortest such path has length dist(u, v) + 2 for d ≥ 6 and dist(u, v) ≥ 3, since one can make a move up, then use an α-edge to move down, after which one can move all the way up to get a path of length dist(u, v) + 2 finishing with the α-edge u-σα (u). Thus all paths on Tα are optimal, and it is easy to see from the above cases that d + 1 is the height of Tα obtained by the algorithm Parent(v, Tα ). Since the fault diameter of Od is d + 1 [13], the height of Tα is optimal.  Theorem 2 The spanning trees Tβ and Tγ with vertex u = 0d−1 1d as root vertex are ISTs for all d ≤ β = γ ≤ 2d − 1. Proof As proven in Lemma 4, Tβ and Tγ are spanning trees. Let v = u be an arbitrary vertex in Od . First we find the representation of the path from u to v in Tα given by the algorithm. Let x be the number of left rotations of either H2 or H4 bringing α to be the first element in either LRx (H2 ) or LRx (H4 ). Note that the algorithm starts from vertex v, but the representations we obtain are for the path from u to v. If v falls under Case 1, then the algorithm picks the last element of LRx (H1 ), then it falls under Case 2, so it picks the last element of LRx (H4 ). However, in the

222

J.-S. Kim et al.

meantime H2 and H4 got switched, so it really was the last element of LRx (H2 ). Then the vertex falls under Case 1 again (unless we reached u), so this process is repeated. Hence elements of LRx (H1 ) and LRx (H2 ) are picked alternately, so P is represented by LRx (H2 ) ⊗ LRx (H1 ). If v falls under Case 2, then the algorithm picks the last element of LRx (H4 ), say st , then it falls under Case 1 with H4 − st as the new H2 , and H3 as the new H1 unless st = α and we reached u. Let x  be the number of left rotations of H4 − st bringing α to be the first element in LRx  (H4 − st ). Then by Case 1, the rest of path P is represented by LRx  (H4 − st ) ⊗ LRx  (H3 ), so overall path P is represented by [LRx  (H4 − st ) ⊗ LRx  (H3 ), st ] = LRx (H4 ) ⊗ LRx  (H3 ). For example, if v = 00111111000 in O6 , and α = 8, then H3 = 1, 2, H4 = 6, 7, 8, and x = 2, thus LRx (H3 ) = 1, 2, LRx (H4 ) = 8, 6, 7, so st = 7. Then H4 − st = 6, 8, so x  = 1, and LRx  (H4 − st ) = 8, 6, LRx  (H3 ) = 2, 1, and P is represented by LRx (H4 ) ⊗ LRx  (H3 ) = [8, 2, 6, 1, 7] (note that LRx (H4 ) ⊗ LRx (H3 ) = [8, 1, 6, 2, 7], so the only difference is that elements at even positions get cyclically permuted). If v falls under Case 3, then the algorithm picks the last element of LRx (H4 ), say st , then it falls under Case 1. Let x  be the number of left rotations of H4 − st bringing α to be the first element in LRx (H4 − st ). Then similarly to the previous case, path P is represented by LRx (H4 ) ⊗ LRx  (H3 ). If v falls under Case 4, then the algorithm picks the last element of LRx (H1 ), say st , then it falls under Case 2 or Case 3. In either case we get that path P is represented by LRx (H2 ) ⊗ LRx (H1 ). If v falls under Case 5, then the algorithm picks α, then falls under Case 2 with H2 ∪ α as the new H4 , and H1 as the new H3 . Let x  be the number of left rotations of H2 ∪ α bringing α to be the first element in LRx  (H2 ∪ α), let st be the last element of LRx  (H2 ∪ α), and let x  be the number of left rotations of H2 ∪ α − st bringing α to be the first element in LRx  (H2 ∪ α − st ). Then by Case 2, path P is represented by [LRx  (H2 ∪ α) ⊗ LRx  (H1 ), α]. For example, if v = 11000001111 in O6 , and α = 8, then H1 = 1, 2, H2 = 6, 7, H4 = 8, 9, 10, 11, thus x = 0. The algorithm first picks α = 8 to get to Case 2, so H2 ∪ α = 6, 7, 8, then x  = 2, thus LRx  (H2 ∪ α) =

8, 6, 7, and st = 7. Then H2 ∪ α − st = 6, 8, so x  = 1, and LRx  (H1 ) = 2, 1, and P is represented by [LRx  (H2 ∪ α) ⊗ LRx  (H1 ), α] = [8, 2, 6, 1, 7, 8]. If v falls under Case 6, then the algorithm picks the first element of LRx (H1 ), say s1 , then falls under Case 5 with H3 ∪ s1 as the new H1 , and H4 as the new H2 . Thus by the previous case, P is represented by [LRx  (H4 ∪ α) ⊗ LRx  (H3 ∪ s1 ), α, s1 ]. For example, if v = 01111110000 in O6 , and α = 8, then H1 = 2, 3, 4, 5, H2 =

8, 9, 10, 11, H3 = 1, and H4 = 6, 7, so x = 0 and s1 = 2. Thus H3 ∪ s1 =

1, 2, so by the previous case again x  = 2, x  = 1, and P is represented by [8, 2, 6, 1, 7, 8, 2]. These cases are summarized in Table 2. Now let the path from vertex u to vertex v in Tβ be P , and the path from vertex u to vertex v in Tγ be Q. Let ψ be the length of P and let ϕ be the length of Q. We prove that Tβ and Tγ are ISTs by proving that there are no common edges on P and Q. Let x be the number of left rotations of H2 or H4 bringing β to be the first element in either LRx (H2 ) or LRx (H4 ), and a be the corresponding number for γ . We will use x  , x  , a  , and a  when appropriate. By the length of the paths P and Q, we consider the following cases:

Optimal Independent Spanning Trees on Odd Graphs

223

Table 2 Summary of the paths from u to v in Tα Case

α∈

Level of v in Od

1

H2

ev = |H1 ∪ H2 |

LRx (H2 ) ⊗ LRx (H1 )

2

H4

od = |H3 ∪ H4 |

LRx (H4 ) ⊗ LRx  (H3 )

3

H4

ev = |H1 ∪ H2 | = d − 1

LRx (H4 ) ⊗ LRx  (H3 )

4

H2

od = |H3 ∪ H4 | ≥ d − 2

LRx (H2 ) ⊗ LRx (H1 )

5

H4

ev = |H1 ∪ H2 | ≤ d − 2

[LRx  (H2 ∪ α) ⊗ LRx  (H1 ), α]

6

H2

od = |H3 ∪ H4 | < d − 2

[LRx  (H4 ∪ α) ⊗ LRx  (H3 ∪ s1 ), α, s1 ]

Path to v in Tα

1. ϕ = ψ = dist(u, v) (v falls under Case 1 or 2 for both P and Q in Parent(v, Tα )): By the algorithm, P is represented by LRx (H2 ) ⊗ LRx (H1 ), and Q by LRa (H2 ) ⊗ LRa (H1 ) (Case 1), or P by LRx (H4 ) ⊗ LRx  (H3 ), and Q by LRa (H4 ) ⊗ LRa  (H3 ) (Case 2). Since β = γ , we have a = x, and hence the numbers at the odd positions in Q are obtained by rotating the numbers at the odd positions in P by |a − x| left or right, and by |a  − x  | for the numbers at even positions. By Lemma 3, connecting P and Q gives a cycle; this means there are no common edges on P and Q. 2. ϕ = ψ + 1 (dist(u, v) = d − 1): By the algorithm, P is represented by LRx (H2 ) ⊗ LRx (H1 ) and Q by LRa (H4 ) ⊗ LRa  (H3 ) or P by LRx (H4 ) ⊗ LRx  (H3 ), and Q by LRa (H2 ) ⊗ LRa (H1 ). That is, v falls under Case 1 in Parent(v, Tα ) for P , and under Case 3 for Q, or it falls under Case 2 for P , and under Case 4 for Q. Therefore it is clear that there are no common edges on P and Q. 3. ϕ = ψ + 2 (v falls under Case 5 for Q, Case 1 for P in Parent(v, Tα )): By the algorithm, the first and the last edges of Q are γ -edges, so let Q = [γ , Q , γ ]. Then the lengths of P and Q are the same. By the algorithm, Paγ (v) in Tγ is connected to v by a γ -edge, so Paγ (v) = σγ (v). Hence, starting from u, the paths [P , γ ] and [γ , Q ] both end up at vertex σγ (v). Since γ is at the beginning of [γ , Q ] and at the end of [P , γ ], Lemma 3 implies that connecting them gives a cycle, which means that there are no common edges on P and Q. 4. ϕ = ψ + 3 (v ∈ Lod and dist(u, v) = d − 2, v falls under Case 4 for Q, Case 2 for P ): By the algorithm, P is represented by LRx (H4 ) ⊗ LRx  (H3 ) and Q by LRa (H2 ) ⊗ LRa (H1 ). Therefore it is clear that there are no common edges on P and Q. 5. ϕ = ψ + 4 (v falls under Case 6 for Q, Case 2 for P in Parent(v, Tα )): By the algorithm, the first edge of Q is a γ -edge, the edge connecting v and Paγ (v) is an s1 -edge, and the edge connecting Paγ (v) and Paγ (Paγ (v)) is also a γ -edge, thus Paγ (Paγ (v)) = σγ (σs1 (v)). Let Q = [γ , Q , γ , s1 ]. Then the length of Q is one more than the length of P , and starting from u, the paths [P , s1 , γ ] and [γ , Q ] both end up at vertex σγ (σs1 (v)). By the algorithm, in the path [γ , Q ] from vertex u to vertex σγ (σs1 (v)), the path [γ , Q ] is represented by LRa  (H4 ∪ γ ) ⊗ LRa  (H3 ∪ s1 ), and in the path [P , s1 , γ ] the subpath P is represented by LRx (H4 ) ⊗ LRx  (H3 ). Though a  = x is possible, since γ is the first element in [γ , Q ] and the last in [P , s1 , γ ], by Lemma 3, connecting [γ , Q ] and [P , s1 , γ ] gives a cycle; this means that there are no common edges on P and Q.

224

J.-S. Kim et al.

6. ϕ = ψ > dist(u, v): This means that both P and Q are obtained as described above in Cases 2–5 for Q. Thus a = x, and it is easy to see that in each case P and Q have no common edges. As proved above, Tβ and Tγ are ISTs.



Combining Lemma 4 and Theorem 2 gives the following theorem. Theorem 3 The algorithm of constructing d ISTs of Od described above can be done   in O(dN) time, where N = 2d−1 . d 4 Conclusion The use of multiple independent spanning trees for data broadcasting in networks provides a number of advantages, including increased fault-tolerance and bandwidth, when the connectivity of the underlying network permits such trees to be defined. Moreover, the presence of independent spanning trees with lower height will be helpful for reducing the number of steps in data transmitting. Hence, in the design of routing schemes for data networks, constructing multiple independent spanning trees with reduced heights is an important issue. In this paper, we presented the construction algorithm of ISTs on odd graphs. We proved that the lengths of the paths in the ISTs are less than or equal to the length of the shortest path + 4 and the heights of the ISTs we constructed are d + 1, which is optimal. Acknowledgements We would like to thank the referees and the editor for a number of helpful comments and suggestions.

References 1. Bao F, Igarashi Y, Öhring SR (1998) Reliable broadcasting in product networks. Discrete Appl Math 83:3–20 2. Biggs N (1979) Some odd graph theory. Ann NY Acad Sci 319:71–81 3. Cheriyan J, Maheshwari SN (1988) Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J Algorithms 9:507–537 4. Curran S, Lee O, Yu X (2006) Finding four independent trees. SIAM J Comput 35:1023–1058 5. Ge Z, Hakimi SL (1997) Disjoint rooted spanning trees with small depths in de Bruijn and Kautz graphs. SIAM J Comput 26:79–92 6. Ghafoor A, Bashkow TR (1991) A study of odd graphs as fault-tolerant interconnection networks. IEEE Trans Comput 40(2):225–232 7. Hasunuma T, Nagamochi H (2001) Independent spanning trees with small depths in iterated line digraphs. Discrete Appl Math 110:189–211 8. Hsieh S-Y, Tu C-J (2009) Constructing edge-disjoint spanning trees in locally twisted cubes. Theor Comput Sci 410:926–932 9. Huck A (1994) Independent trees in graphs. Graphs Comb 10:29–45 10. Huck A (1999) Independent trees in planar graphs. Graphs Comb 15:29–77 11. Itai A, Rodeh M (1988) The multi-tree approach to reliability in distributed networks. Inf Comput 79:43–59 12. Iwasaki Y, Kajiwara Y, Obokata K, Ugarashi Y (1999) Independent spanning trees of chordal rings. Inf Process Lett 69:155–160

Optimal Independent Spanning Trees on Odd Graphs

225

13. Kim J-S, Lee H-O (2008) Comments on “A study of odd graphs as fault-tolerant interconnection networks. IEEE Trans Comput 57(6):864 14. Kim J-S, Lee H-O (2008) One-to-all broadcasting of odd networks for one-port and all-port models. ETRI J 30(6):856–858 15. Kim J-S, Cheng E, Lipták L, Lee H-O (2009) Embedding hypercubes, rings and odd graphs into hyper-stars. Int J Comput Math 86:771–778 16. Meredith GHJ, Llyod EK (1972) The Hamiltonian graphs O4 to O7 . In: Welsh DJA, Woodal DR (eds) Combinatorics. Institute of Mathematics and Applications, Southend-On-Sea, pp 229–236 17. Miura K, Takahashi D, Nakano S, Nishizeki T (1999) A linear-time algorithm to find four independent spanning trees in four-connected planar graphs. Int J Found Comput Sci 10:195–210 18. Nagai S, Nakano S (2000) A linear-time algorithm to find independent spanning trees in maximal planar graphs. In Proceedings of 26th workshop on graph—theoretic concepts in computer science, WG 2000. LNCS, vol 1928, pp 290–301 19. Obokata K, Iwasaki Y, Bao F, Igarashi Y (1996) Independent spanning trees of product graphs and their construction. IEICE Trans Fundam Electron Commun Comput Sci E79-A:1894–1903 20. Parhami B, Kwai D-M (2001) Unified formulation of honeycomb and diamond networks. IEEE Trans Parallel Distrib Syst 12(1):74–80 21. Tang S-M, Wang Y-L, Leu Y-H (2004) Optimal independent spanning trees on hypercubes. J Inf Sci Eng 20:143–155 22. Tang S-M, Yang J-S, Wang Y-L, Chang J-M (2009) Independent spanning trees on multidimensional torus networks. IEEE Trans Comput (to appear) 23. Yang J-S, Tang S-M, Chang J-M, Wang Y-L (2007) Parallel construction of optimal independent spanning trees on hypercubes. Parallel Comput 33:73–79 24. Yang J-S, Chang J-M, Tang S-M, Wang Y-L (2007) Reducing the height of independent spanning trees in chordal rings. IEEE Trans Parallel Distrib Syst 18(5):644–657 25. Yang J-S, Chang J-M, Tang S-M, Wang Y-L (2009) On the independent spanning trees of recursive circulant graphs G(cd m , d) with d > 2. Theor Comput Sci 410:2001–2010 26. Yang J-S, Chang J-M, Tang S-M, Wang Y-L (2009) Constructing multiple independent spanning trees on recursive circulant graphs G(2m , 2). Int J Found Comput Sci (to appear) 27. Zehavi A, Itai A (1989) Three tree-paths. J Graph Theory 13:175–188