Shuo-I Wang

Fu-Hsing Wang
email: wang.fuhsing@gmail.com

Linear time algorithms for finding independent spanning trees on pyramid networks †

Keywords: independent spanning trees, interconnection networks, pyramid networks, graph algorithms

The use of independent spanning trees (ISTs) has scientific applications in faulttolerant requirement in network protocols and secure message distributions. Most of the designs of ISTs are for those interconnection networks with vertex symmetric property, implying that one can find ISTs rooted on a designated vertex, and, by the vertex symmetry property of the given network, hence have solved the ISTs problem on any arbitrary vertex. The existence of asymmetry makes the ISTs problem even harder than its symmetric counterpart. In this paper, we propose linear time algorithms that solved 3-ISTs rooted at an arbitrary vertex of pyramid networks.

Introduction

The vertex set and the edge set of a graph G are denoted by V (G) and E(G), respectively. Let P = v 1 , v 2 , . . . , v j be a path from v 1 to v j in G. We use I(P ) to denote the set V (P ) \ {v 1 , v j }.

Two paths P and Q are called disjoint, denoted by P Q, if V (P ) ∩ V (Q) = ∅. We say that P and Q are internally disjoint if I(P ) ∩ I(Q) = ∅. A spanning tree of a graph G is a tree T such that V (T ) = V (G). Given a designated vertex r ∈ V as a root vertex and a natural number k, spanning trees T 1 , T 2 , . . . , T k of G are called k-independent spanning trees of G rooted at r (refered as k-ISTs for short) if the k paths connecting r and v, for any vertex v, in T 1 , T 2 , . . . , T k are pairwise internally disjoint in G.

The use of independent spanning trees has scientific applications in fault-tolerant requirement in network protocols and secure message distributions [START_REF] Bao | Reliable broadcasting and secure distributing in channel networks[END_REF]. For example, an efficient and reliable broadcasting can be achieved by sending k copies of the message rooted at the source vertex along k-ISTs such that the message can be broadcasted to all the other vertices in a network with at most k -1 faulty vertices. Although the ISTs problem is hard for general graphs, several results are known for some special classes of graphs, especially on interconnection networks, such as odd graphs [START_REF] Kim | Optimal independent spanning trees on odd graphs[END_REF],

n-dimensional torus [START_REF] Tang | Independent spanning trees on multidimensional torus networks[END_REF], product graphs [START_REF] Obokata | Independent spanning trees of product graphs and their construction[END_REF], chordal rings [START_REF] Iwasaki | Independent spanning trees of chordal rings[END_REF], recursive circulant graphs [START_REF] Yang | On the independent spanning trees of recursive circulant graphs G(cd m ; d) with d > 2[END_REF], parity cubes [START_REF] Wang | An algorithm to construct independent spanning trees on parity cubes[END_REF], and hypercubes [START_REF] Tang | Optimal independent spanning trees on hypercubes[END_REF]. Most of the above results are for symmetric graphs implying that one can find ISTs rooted on a designated vertex, and, by the vertex symmetry property of the given graph, hence have solved the ISTs problem on any arbitrary vertex. However, the investigation into the ISTs problem on interconnection networks with no vertex symmetric property, to the best of our knowledge, are poor.

We focus attention on the construction of ISTs of a given pyramid network. Pyramid networks have potentially powerful architecture for many applications such as image processing, visualization, and data mining [START_REF] Culler | Parallel Computer Architecture: A Hardware/Software Approach[END_REF]. The major advantage of pyramids which is important for image processing systems is hierarchical abstracting and transferring the data from different directions and forward them toward the apex of a pyramid [START_REF] Shahhoseini | Nonflat surface level pyramid: a high connectivity multidimensional interconnection network[END_REF]. A pyramid network is a 3-connected graph. In [START_REF] Cheriyan | Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs[END_REF], Cheriyan and Maheshwari showed that, for any 3-connected graph, 3-ISTs rooted at any vertex can be found in O(|V ||E|) time. In this paper, we propose linear time algorithms for finding 3-ISTs of a pyramid network rooted at an arbitrary vertex.

Preliminaries

All graphs considered here are finite, undirected, without loops and multiple edges. A path in a graph G is a single vertex or a sequence of distinct vertices v 1 , v 2 , . . . , v n such that (v 1 , v 2 ), (v 2 , v 3 ), . . . , (v n-1 , v n ) are edges of G and the v i are distinct. A vertex of degree 0 is considered as an isolated vertex.

A 2 k × 2 k square mesh, denoted by M k , has the vertex set V (M k ) = {(x, y) | 0 ≤ x, y ≤ 2 k -1} where any two vertices (x 1 , y 1 ) and (x 2 , y 2 ) are connected by an edge iff |x 1 -

x 2 | + |y 1 -y 2 | = 1.
Each M k , k ≥ 2, can be partitioned into 2 k-2 × 2 k-2 square submeshes M 2 and each M 2 is called a cluster. Every cluster can be further decomposed into 2 × 2 M 1 and each M 1 is said to be a block. Let v, v + , v ++ , v -denote the four vertices of a block in a clockwise order starting from v, and B, B + , B ++ , B -denote the four blocks of a cluster in a clockwise order starting from B.

Let P n be an n-dimensional pyramid with the vertex set n k=0 V k , where V k = {(k; x, y) | 0 ≤ x, y ≤ 2 k -1}. Vertex (0; 0, 0) is the apex of P n and also denoted as ∆. The subgraph induced by V k is connected as an M k and called layer k of P n . Let S 0 and S 1 denote the layers 0 and 1 of P n with the vertex set (0; 0, 0) and {(1; x, y) | 0 ≤ x, y ≤ 3}, respectively. Let S(k; a, b) denote the cluster on layer k with the vertex set {(k; x, y) | 4a ≤ x ≤ 4a + 3 and 4b ≤ y ≤ 4b + 3}, where 2 ≤ k ≤ n and 0 ≤ a, b ≤ 2 k-2 -1. Notice that layer k has 2 k-2 clusters. Vertex (k; x, y) has exactly four children (k + 1; 2x, 2y), (k + 1; 2x, 2y + 1), (k + 1; 2x + 1, 2y), (k + 1; 2x + 1, 2y + 1) in V k+1 and a parent vertex (k -1; x 2 , y 2 ) in V k-1 . For simplicity, we shall use the abbreviated notation S k for S(k; a, b), whenever no confusion can arise. Let p(v) denote the parent vertex of v and l(v) the layer number of v. The block containing the four children of v, denoted C B (v), is called the child block of v. In an S k , the block with the vertex set {p(v)|v ∈ V (S k+1 )} is called the parent block of S k+1 and denoted by P B (S k+1 ). An edge between v and p(v) is called a layer edge, while every edge of a cluster is called a cluster edge. Every vertex on the shortest path from v to ∆ is called an ancestor of v.

In a cluster S, every vertex of degree 4 is called an inner vertex, while the remaining vertices of S are said to be outer vertices. An outer vertex of degree 2 is also called a corner vertex. The subgraph induced by all inner vertices of S is an i-cycle, while the cycle induced by all of the outer vertices is an o-cycle. For any two vertices u and v in an o-cycle (respectively, i-cycle) O, each path from u to v is called an o-path (respectively, i-path). Vertex v is also labeled as u +d (respectively, u -d ) if v can be visited from u via d edges of O in a clockwise order (respectively, a counterclockwise order).

In paricular, u = v if d = 0. Figure 1 depicts an example of a 2-layered pyramid P 2 . The dash lines indicate layer edges, while the solid lines are cluster edges. Each bold 4-cycle is a block. The top-right block of S(2; 0, 0) has a corner vertex (2; 0, 3), an inner vertex (2; 1, 2) and outer vertices (2; 0, 3), (2; 1, 3) and (2; 0, 2). The subgraph induced by the set X = {(2; 1, 1), (2; 1, 2), (2; 2, 2), (2; 2, 1)} is the i-cycle of S(2; 0, 0), and the o-cycle of S(2; 0, 0) is induced by V (S(2; 0, 0)) \ V (X).

Constructions of 3-ISTs Rooted at Different Layers

For a given root vertex r, we shall construct 3-ISTs of P n rooted at r by considering the position of r to fulfill the vertex asymmetry of P n .

Rooted at the Apex

Before the construction of 3-ISTs of P n rooted at an arbitrary vertex, we first define a vertex coloring on every vertex of P n for selecting edges to be tree edges of a spanning tree. Let π 0 :

V → {0, 1, 2, 3} be a coloring on P n , where for each vertex v ∈ V (P n -r), π 0 (v) ∈ {0, 1, 2, 3}, and the four vertices of each block are assigned distinct colors. For convenience, let ρ 1 , ρ 2 and ρ 3 be three distinct color numbers in {1, 2, 3} in the remaining text. In S 1 , we arbitrarily select a vertex v as the corner vertex and then assign colors 0, ρ 1 , ρ 2 and ρ 3 to vertices v, v + , v -and v ++ , respectively. Let Ĥ1,ρ i be the subgraph with the vertex set V (S 1 ) ∪ {r}, where 1 ≤ i ≤ 3.

And let

E( Ĥ1,ρ 1 ) = E( v ++ , v + , v, v -) ∪ {(r, v + )}, E( Ĥ1,ρ 2 ) = E( v ++ , v -, v, v + ) ∪ {(r, v -)} and E( Ĥ1,ρ 3 ) = E( v + , v ++ , v -) ∪ {(r, v), (r, v ++ )}.
The π 0 coloring of a cluster is determined by the coloring of its parent block. For a cluster S k , k ≥ 2, let x, x + , x -and x ++ be the four parent vertices We now define three graphs for any cluster, and then each subgraph will be selected to be

of S k such that π 0 (x) = 0, π 0 (x + ) = ρ 1 , π 0 (x -) = ρ
Input: Given a coloring on the vertices x, x + , x -, x ++ of P B (S k ) as:

π 0 (x) = 0, π 0 (x + ) = ρ 1 , π 0 (x -) = ρ 2 , π 0 (x ++ ) = ρ 3 . Output: The colorings of blocks C B (x), C B (x + ), C B (x -) and C B (x ++ ) in S k . begin
Let the inner vertex of C B (x ++ ) be ĥk,ρ3 and the corner vertices of C B (x + ) and C B (x -) be ĥk,ρ1 and ĥk,ρ2 , respectively;

Assign color ρ 1 to every vertex of { ĥk,ρ1 , ĥ+2 k,ρ1 , ĥ-2 k,ρ1 , ĥ-5 k,ρ1 };

Assign color ρ 2 to every vertex of { ĥk,ρ2 , ĥ+2 k,ρ2 , ĥ-2 k,ρ2 , ĥ-5 k,ρ2 }; Assign color ρ 3 to every inner vertex of S k ; Assign color 0 to every uncolored outer vertex of S k ;

E( Ĥk,ρ1 ) = E(P k,ρ1 ) ∪ {( ĥk,ρ3 , ĥ+2 k,ρ1
), ( ĥ-1 k,ρ3 , ĥ-1 k,ρ1 ), ( ĥ+2 k,ρ3 , ĥ-2 k,ρ1 ), ( ĥ+1 k,ρ3 , ĥ-5 k,ρ1 ), ( ĥk,ρ1 , p( ĥk,ρ1 ))};

E( Ĥk,ρ2 ) = E(P k,ρ2 ) ∪ {( ĥk,ρ3 , ĥ-2 k,ρ2
), ( ĥ-1 k,ρ3 , ĥ-5 k,ρ2 ), ( ĥ+2 k,ρ3 , ĥ+2 k,ρ2 ), ( ĥ+1 k,ρ3 , ĥ-1 k,ρ2 ), ( ĥk,ρ2 , p( ĥk,ρ2 ))};

E( Ĥk,ρ3 ) = E(P k,ρ3 ) ∪ {(u, v) ∈ E(S k )|π 0 (u) = ρ 3 , π 0 (v) = ρ 3 } ∪ {( ĥk,ρ1 , ĥ-1 k,ρ1 ), ( ĥk,ρ2 , ĥ-1 k,ρ2 ), ( ĥ+3 k,ρ1 , p( ĥ+3 k,ρ1
)), ( ĥ-3 k,ρ1 , p( ĥ-3 k,ρ1 )), ( ĥk,ρ3 , p( ĥk,ρ3 ))};

end HFinding Algorithm a subgraph of one of the 3-ISTs of P n . Let Ĥi (k; a, b) denote the subgraph with the vertex set

V (S(k; a, b)) + V (P B (S(k; a, b))), where 1 ≤ i ≤ 3, 2 ≤ k ≤ n and 0 ≤ a, b ≤ 2 k-2 -1. A vertex v ∈ V ( Ĥi (k; a, b)), denoted ĥi (k; a, b), is called a junction vertex of Ĥi (k; a, b) if π 0 (v) = π 0 (p(v)) = i.
The vertex of color ρ i in S 1 is denoted by ĥ1,ρ i for each i and the vertex of color 0 in S 1 is ĥ1,0 .

For simplicity, we shall also use the abbreviated notation ĥk,i and Ĥk,i for ĥi (k; a, b) and Ĥi (k; a, b), respectively, and let ĥk = { ĥk,1 , ĥk,2 , ĥk,3 }.

By the first statement of HFinding Algorithm, there are exactly two junction vertices on the o-cycle of S k , while one junction vertex belongs to the i-cycle of S k . In Statements 6-8, we define three subgraphs Ĥk,ρ 1 , Ĥk,ρ 2 and Ĥk,ρ 3 on S k . Ĥk,ρ 1 has the outer path ). Ĥk,ρ 3 has the inner path P k,ρ 3 = ĥ-3 k,ρ 3 , ĥ-2 k,ρ 3 , ĥ-1 k,ρ 3 , ĥk,ρ 3 and every outer vertex v ∈ V (S k ) has an edge incident to P k,ρ 3 if v is not a corner vertex. Among the four corner vertices of S k , ĥk,ρ 1 and ĥk,ρ 2 are adjacent to ĥ-1 k,ρ 1 and ĥ-1 k,ρ 2 , respectively, in Ĥk,ρ 3 . And the two corner vertices of color 0 have layer edges ( ĥ+3 k,ρ 1 , p( ĥ+3 k,ρ 1 )) and ( ĥ-3 k,ρ 1 , p( ĥ-3 The following observation gives some properties of ĥk,ρ 1 and ĥk,ρ 2 :

P k,ρ 1 = ĥk,ρ 2 , ĥ-5 k,ρ 1 , . . . , ĥ-1 k,ρ 1 , ĥk,ρ 1 , ĥ+1 k,ρ 1 , ĥ+2 k,ρ 1 , . . . , ĥ+5 k,ρ
Observation 3.1. Let ĥk,ρ 1 and ĥk,ρ 2 be on the o-cycle of S k , where 2 ≤ k ≤ n.

( ( Q. E. D.

) ĥ+d k,ρ 1 = ĥ-(6-d) k,ρ 2 and ĥ+d k,ρ 2 = ĥ-(6-d) k,ρ 1 . ( 1
) If v = ĥ+d k,ρ 1 , then v is an end-vertex of ĥ+d k,ρ 1 , ĥ+(d-1) 2
) If v = ĥ-d k,ρ 1 , then v is an end-vertex of ĥ-d k,ρ 3
Since the π 0 coloring of a cluster can be decided by its parent block, the coloring of S 2 is determined by the coloring of S 1 . After that, the coloring and subgraphs of every cluster in P n can then be established. We now continue with the derivation of building spanning subgraphs

T 0 ρ i , i = 1, 2, 3, on P n . Each T 0 ρ i is regarded as an n-layered graph. Let V (T 0 ρ i ) = V (P n ) and E(T 0 ρ i ) = E( Ĥ1,ρ i ) n k=2 2 k-2 -1 a,b=0 E( Ĥρ i (k; a, b)) for i = 1, 2, 3.
To show that there are three pairwise internally disjoint paths from any vertex u k to the apex r, we first find three pairwise internally disjoint paths from u k to the block B containing p(u k ). andu k-1 is a dummy vertex with dummy edges incident to every vertex of P B (S k ), then paths from u k to u k-1 in T 0 1 , T 0 2 and T 0 3 are pairwise internally disjoint.

Lemma 3.1. If u k is a vertex of S k , 2 ≤ k ≤ n,
Proof. Let ĥk,ρ 1 and ĥk,ρ 2 be outer vertices and ĥk,ρ 3 be an inner vertex. Since ĥk,ρ 1 , ĥk,ρ 2 and ĥk,ρ 3 belong to three different blocks, p( ĥk,ρ 1 ), p( ĥk,ρ 2 ) and p( ĥk,ρ 3 ) are distinct. Let P ρ i be the path from u k to u k-1 in T 0 ρ i , where 1 ≤ i ≤ 3. Each P ρ i can be regarded as a concatenation of subpaths

u k Q ρ i t i , u k-1
, where t i ∈ V (P B (S k )). Let v i be the neighbor of u k in Ĥk,ρ i for each i. Note that v i = v j and t i = t j if i = j. We shall prove Q ρ 1 , Q ρ 2 , Q ρ 3 pairwise disjoint instead of showing P ρ 1 , P ρ 2 , P ρ 3 pairwise internally disjoint.

Case 1. u k is a corner vertex and π 0 (u k ) = 0.

By HFinding Algorithm, u k is either ĥ+3 k,ρ 1 or ĥ-3

k,ρ 1 . From the definition of E( Ĥk,ρ 3 ), (u k , p(u k )) ∈ E( Ĥk,ρ 3 ). Then P ρ 3 = u k , p(u k ), u k-1 and thus Q ρ 3 is empty. So, Q ρ 3 Q ρ 1 and Q ρ 3 Q ρ 2 . If u k = ĥ+3 k,ρ 1 , by Observation 3.1 (2), u k is an end-vertex of ĥ+3 k,ρ 1 , ĥ+2 k,ρ 1 , ĥ+1 k,ρ 1 , ĥk,ρ 1 in Ĥk,ρ 1 and
is also an end-vertex of ĥ-3

k,ρ 2 , ĥ-2 k,ρ 2 , ĥ-1 k,ρ 2 , ĥk,ρ 2 in Ĥk,ρ 2 . It means that Q ρ 1 = ĥ+2 k,ρ 1 , ĥ+1 k,ρ 1 , ĥk,ρ 1 and Q ρ 2 = ĥ-2 k,ρ 2 , ĥ-1 k,ρ 2 , ĥk,ρ 2 . For the case u k = ĥ-3 k,ρ 1 , by Observation 3.1 (3), u k is an end- vertex of ĥ-3 k,ρ 1 , ĥ-2 k,ρ 1 , ĥ-1 k,ρ 1 , ĥk,ρ 1 in Ĥk,ρ 1 and an end-vertex of ĥ+3 k,ρ 2 , ĥ+2 k,ρ 2 , ĥ+1 k,ρ 2 , ĥk,ρ 2 in Ĥk,ρ 2 . Then Q ρ 1 = ĥ-2 k,ρ 1 , ĥ-1 k,ρ 1 , ĥk,ρ 1 and Q ρ 2 = ĥ+2 k,ρ 2 , ĥ+1 k,ρ 2 , ĥk,ρ 2 . It concludes that Q ρ 1 Q ρ 2 for cases u k = ĥ+3 k,ρ 1 and u k = ĥ-3 k,ρ 1 . Case 2. u k = ĥk,ρ 1 .
Obviously,

P ρ 1 = u k , p(u k ), u k-1 and thus Q ρ 1 is empty. So, Q ρ 1 Q ρ 2 and Q ρ 1 Q ρ 3 . Furthermore,
since ĥk,ρ 1 and ĥ+5 k,ρ 2 are the two end-vertices of the path P k,ρ 2 and ĥk,ρ

2 ∈ V (P k,ρ 2 ), Q ρ 2 is a subpath of P k,ρ 2 and Q ρ 2 does not contain the vertex ĥ+5 k,ρ 2 .
From the definition of Ĥk,ρ 3 , ĥk,ρ 1 and ĥ-1 k,ρ 1 are adjacent and ĥ-1

k,ρ 1 is adjacent to an inner vertex v in E( Ĥk,ρ 3 ). Since v ∈ V (P k,ρ 3 ), Q ρ 3 -ĥ-1 k,ρ 1 is a subpath of P k,ρ 3 . That is, Q ρ 3 -ĥ+5 k,ρ 2 is a subpath of P k,ρ 3 because ĥ-1 k,ρ 1 = ĥ+5 k,ρ 2 . Moreover, since P k,ρ 3 P k,ρ 2 and ĥ+5 k,ρ 2 ∈ V (Q ρ 2 ), Q ρ 3 Q ρ 2 . Case 3. u k = ĥk,ρ 2 .
The proof is similar to Case 1 and is left to the reader.

Case 4. u k is an inner vertex.

Notably, v 1 and v 2 belong to the same block. If u k = ĥk,ρ 3 , then Q ρ 3 is empty. By the definitions of Ĥk,ρ 1 and Ĥk,ρ 2 , v 1 and v 2 are ĥ+2 k,ρ 1 and ĥ-2 k,ρ 2 , respectively. Then

Q ρ 1 = ĥ+2 k,ρ 1 , ĥ+1 k,ρ 1 , ĥk,ρ 1 and Q ρ 2 = ĥ-2 k,ρ 2 , ĥ-1 k,ρ 2 , ĥk,ρ 2 . So, Q ρ 1 , Q ρ 2 and Q ρ 3 are pairwise disjoint. Similarly, we get pairwise disjoint paths Q ρ 1 , Q ρ 2 and Q ρ 3 for cases u k = ĥ-j k,ρ 3 , where j = 1, 2, 3. Case 5. u k is adjacent to a corner vertex. Clearly, v i ∈ V (P k,ρ i ) for each i. That is, Q ρ 3 is an i-path, while both Q ρ 1 and Q ρ 2 are o-paths. So, Q ρ 3 Q ρ 1 and Q ρ 3 Q ρ 2 . Vertex u k is either ĥ+d 1 k,ρ 1 or ĥ-d 2 k,ρ 1 , where 1 ≤ d 1 , d 2 ≤ 5 and d 1 , d 2 = 3. For the former case, by Observation 3.1 (1), Q ρ 1 = ĥ+(d 1 -1) k,ρ 1 , . . . , ĥk,ρ 1 and Q ρ 2 = ĥ-(6-d 1 -1) k,ρ 2 , . . . , ĥk,ρ 2 . Thus, Q ρ 1 Q ρ 2 .
For the latter case, by Observation 3.

1 (2), Q ρ 1 = ĥ-(d 2 -1) k,ρ 1 , . . . , ĥk,ρ 1 and Q ρ 2 = ĥ+(6-d 2 -1) k,ρ 2 , . . . , ĥk,ρ 2 . Therefore, Q ρ 1 Q ρ 2 .
Q. E. D.

We further present three pairwise internally disjoint paths from a block B on a cluster S k to

P B (S k ). Lemma 3.2. Let B be a block of S k , 2 ≤ k ≤ n. If u k and u k-1
are dummy vertices with dummy edges incident to every vertex of B and P B (S k ), respectively, then the paths from

u k to u k-1 in T 0 i , for i = 1, 2, 3, are pairwise internally disjoint. Proof. Let V (B) = {v 0 , v ρ 1 , v ρ 2 , v ρ 3 } and V (P B (S k )) = {t 0 , t ρ 1 , t ρ 2 , t ρ 3 }, where π 0 (v 0 ) = π 0 (t 0 ) = 0 and π 0 (v ρ i ) = π 0 (t ρ i ) = ρ i for each i. Let P ρ i denote the path from u k to u k-1 in T 0 ρ i
and Q ρ j be the subpath of P ρ j on S k for each i. Let ĥk,ρ 1 and ĥk,ρ 2 be outer vertices and ĥk,ρ 3 be an inner vertex. By the definition of E( Ĥk,ρ j ), P ρ j must visit v ρ j and t ρ j , where j = 1, 2. We shall

prove Q ρ 1 , Q ρ 2 , Q ρ 3 pairwise disjoint instead of showing P ρ 1 , P ρ 2 , P ρ 3 pairwise internally disjoint.
According to the HFinding Algorithm,

v ρ 1 ∈ { ĥk,ρ 1 , ĥ+2 k,ρ 1 , ĥ-2 k,ρ 1 , ĥ-5 k,ρ 1 } and v ρ 2 ∈ { ĥk,ρ 2 , ĥ+2 k,ρ 2 , ĥ-2 k,ρ 2 , ĥ-5 k,ρ 2 }.
Actually, the ordered pair

(v ρ 1 , v ρ 2 ) ∈ {( ĥk,ρ 1 , ĥ-5 k,ρ 2 ), ( ĥ+2 k,ρ 1 , ĥ-2 k,ρ 2 ), ( ĥ-2 k,ρ 1 , ĥ+2 k,ρ 2 ), ( ĥ-5 k,ρ 1 , ĥk,ρ 2 )}. Since p( ĥk,ρ j ) is t ρ j for each j, we get the ordered pair (Q ρ 1 , Q ρ 2 ) as follows: (Q ρ 1 , Q ρ 2 ) =          ( ĥk,ρ 1 , ĥ-5 k,ρ 2 , ĥ-4 k,ρ 2 , . . . , ĥk,ρ 2 ) if (v ρ 1 , v ρ 2 ) = ( ĥk,ρ 1 , ĥ-5 k,ρ 2 ), ( ĥ+2 k,ρ 1 , ĥ+1 k,ρ 1 , ĥk,ρ 1 , ĥ-2 k,ρ 2 , ĥ-1 k,ρ 2 , ĥk,ρ 2 ) if (v ρ 1 , v ρ 2 ) = ( ĥ+2 k,ρ 1 , ĥ-2 k,ρ 2 ), ( ĥ-2 k,ρ 1 , ĥ-1 k,ρ 1 , ĥk,ρ 1 , ĥ+2 k,ρ 2 , ĥ+1 k,ρ 2 , ĥk,ρ 2 ) if (v ρ 1 , v ρ 2 ) = ( ĥ-2 k,ρ 1 , ĥ+2 k,ρ 2 ), ( ĥ-5 k,ρ 1 , ĥ-4 k,ρ 1 , . . . , ĥk,ρ 1 , ĥk,ρ 2 ) if (v ρ 1 , v ρ 2 ) = ( ĥ-5 k,ρ 1 , ĥk,ρ 2 ).
It is clear that Q ρ 1 Q ρ 2 for each case. Consider P ρ 3 . By the definition of E( Ĥk,ρ 3 ), P ρ 3 visits either t 0 or t ρ 3 .

Case 1. P ρ 3 visits t 0 .

By the definition of E( Ĥk,ρ 3 ),

P ρ 3 = u k , v 0 , t 0 , u k-1 and thus Q ρ 3 = v 0 . Clearly, Q ρ 3 Q ρ 1 and Q ρ 3 Q ρ 2 for every ordered pair (v ρ 1 , v ρ 2 ).
Case 2. P ρ 3 visits both v ρ 3 and t ρ 3 .

Since every vertex of color ρ 3 is an inner vertex, Q ρ 3 is a subpath of P k,ρ 3 and is in fact an i-path.

However, both Q ρ 1 and Q ρ 2 are o-paths. So, Q ρ 3 Q ρ 1 and Q ρ 3 Q ρ 2 .
Case 3. P ρ 3 visits both v 0 and t ρ 3 .

If v 0 is a corner vertex, then v 0 must be ĥ+3 k,ρ 1 and t ρ 3 = p(v 0 ). Since, by the definition of E( Ĥk,ρ 3 ),

( ĥ+3 k,ρ 1 , p( ĥ+3 k,ρ 1 )) ∈ E( Ĥk,ρ 3 ), P ρ 3 = u k , v 0 , t ρ 3 , u k-1 . That is, Q ρ 3 = v 0 . So, Q ρ 3 Q ρ 1 and Q ρ 3 Q ρ 2
for every ordered pair (v ρ 1 , v ρ 2 ). Otherwise, v 0 is not a corner vertex and so v 0 is adjacent to an inner vertex, say v.

Since v ∈ V (P k,ρ 3 ), Q ρ 3 -v 0 is a subpath of P k,ρ 3 . According to HFinding Algorithm, v 0 ∈ { ĥ-1 k,ρ 1 , ĥ-1 k,ρ 2 }. Since both Q ρ 1 and Q ρ 2 are o-paths and neither Q ρ 1 nor Q ρ 2 contains v 0 for every ordered pair (v ρ 1 , v ρ 2 ), Q ρ 3 Q ρ 1 and Q ρ 3 Q ρ 2 .
Q. E. D.

Theorem 3.1. Graphs T 0 1 , T 0 2 and T 0 3 are 3-ISTs of P n rooted at apex.

Proof.

Let ρ 1 , ρ 2 and ρ 3 be color numbers of the vertices v, v + , v -and v ++ in S 1 . Since

E( Ĥ1,ρ 1 ) = E( v ++ , v + , v, v -)∪{(r, v + )}, E( Ĥ1,ρ 2 ) = E( v ++ , v -, v, v + )∪{(r, v -)} and E( Ĥ1,ρ 3 ) = E( v + , v ++ , v -)∪{(r, v), (r, v ++ )}, every Ĥ1,ρ i , i = 1, 2, 3
, is a tree. According to HFinding Algorithm, every Ĥk,i is acyclic, where 2 ≤ k ≤ n. For connectivity, each ĥk,i has a layer edge ( ĥk,i , p( ĥk,i )) ∈ E( Ĥk,i ) for connecting subgraphs Ĥk,i and Ĥk-1,i . It follows that T 0 i is a tree. Actually, T 0 i is a spanning tree of P n due to

V (T 0 i ) = V (P n ).
For any vertex u k = (k; x, y) ∈ V (P n ), we now want to find three pairwise internally disjoint paths from u k to the apex r. The case

u k = (0; 0, 0) is trivial. Consider k = 1. If u k = ĥ1,0 ,
we get three pairwise internally disjoint paths u k , ĥ1,ρ 1 , r , u k , ĥ1,ρ 2 , r and u k , r from u k to r in T 0 ρ 1 , T 0 ρ 2 and T 0 ρ 3 , respectively. Similarly, we get three pairwise internally disjoint paths u k , r , u k , ĥ1,0 , ĥ1,ρ 2 , r and u k , ĥ1,ρ 3 , r for the case u k = ĥ1,ρ 1 ; paths u k , ĥ1,ρ 0 , ĥ1,ρ 1 , r , u k , r and u k , ĥ1,ρ 3 , r for u k = ĥ1,ρ 2 ; and paths u k , ĥ1,ρ 1 , r , u k , ĥ1,ρ 2 , r and u k , r for u k = ĥ1,ρ 3 .

For k ≥ 2, let u j be the dummy vertex with dummy edges incident to every vertex of P B (S j+1 ), where 1 ≤ j ≤ k -1. From Lemma 3.1, we get pairwise internally disjoint paths X k,ρ i from u k to u k-1 in T 0 ρ i for each i = 1, 2, 3. By applying Lemma 3.2, we get pairwise internally disjoint paths

X j,ρ i from u j to u j-1 in T 0 ρ i for each i, where 2 ≤ j ≤ k -1. Moreover, since ( ĥ1,ρ i , r) ∈ E( Ĥ1,ρ i ),
we get three pairwise internally disjoint paths from u k to r.

Q. E. D. Q. E. D.

Rooted at a Vertex on Layer 1

In S 1 , we let r as the corner vertex and assign colors 0, ρ 1 , ρ 2 and ρ 3 to vertices r, r + , r -and r ++ , respectively. Due to r ∈ V (S 1 ), r + , r -and r ++ are actually ĥ1,ρ 1 , ĥ1,ρ 2 and ĥ1,ρ 3 , respectively. To color V (P n ), we also apply HFinding Algorithm iteratively on every block of P n . Since the coloring of a cluster can be decided by its parent block, the π 0 coloring of S 2 is determined by the coloring of S 1 . In this way, the coloring and subgraphs of every cluster of P n can be established.

Let Ĥ1 1,ρ i have the vertex set V (S 1 ) ∪ {∆}. Let E( Ĥ1 1,ρ 1 ) = E( r -, r ++ , r + , r ) ∪ {(r + , ∆)}, E( Ĥ1 1,ρ 2 ) = E( r + , r ++ , r -, r ) ∪ {(r -, ∆)} and E( Ĥ1 1,ρ 3 ) = {{(v, ∆)|v ∈ V (S 1 )}. Notations S k , ĥk,i and Ĥk,i , where 2 ≤ k ≤ n and 1 ≤ i ≤ 3, refer to Section 3.1. Let V (T 1 i ) = V (P n ) and E(T 1 i ) = E( Ĥ1 1,i ) n k=2 2 k-2 -1 a,b=0
E( Ĥi (k; a, b)) for each i.

Theorem 3.3. Graphs T 1 1 , T 1 2 and T 1 3 are 3-ISTs of P n rooted at a vertex of S 1 .

Proof. Let 0, ρ 1 , ρ 2 and ρ 3 be color numbers of the vertices r, r + , r -and r ++ in S 1 . Since

E( Ĥ1 1,ρ 1 ) = E( r -, r ++ , r + , r )∪{(r + , ∆)}, E( Ĥ1 1,ρ 2 ) = E( r + , r ++ , r -, r )∪{(r -, ∆)} and E( Ĥ1 1,ρ 3 ) = {{(v, ∆)|v ∈ V (S 1 )}, every Ĥ1 1,i , i = 1, 2, 3
, is a tree. According to HFinding Algorithm, every Ĥk,i is acyclic, where 2 ≤ k ≤ n. For connectivity, each ĥk,i has a layer edge ( ĥk,i , p( ĥk,i )) ∈ E( Ĥk,i ) for connecting subgraphs Ĥk,i and Ĥk-1,i , where 3 ≤ k ≤ n. In addition, each ĥ2,i has a layer edge ( ĥ2,i , p( ĥ2,i )) ∈ E( Ĥ2,i ) for connecting subgraphs Ĥ2,i and Ĥ1 1,i . It follows that T 1 i is a tree.

Actually, T 1 i is a spanning tree of P n due to V (T 1 i ) = V (P n ).

For any vertex u k = (k; x, y) ∈ V (P n ), we now want to find three pairwise internally disjoint paths from u k to r. If u k is ∆, by the definition of each Ĥ1 1,ρ i , we have pairwise internally paths For k ≥ 2, let u j be the dummy vertex with dummy edges incident to every vertex of P B (S j+1 ), where 1 ≤ j ≤ k -1. From Lemma 3.1, we get pairwise internally disjoint paths X k,ρ i from u k to u k-1 in T 1 ρ i for each i = 1, 2, 3. By applying Lemma 3.2, we get pairwise internally disjoint paths X j,ρ i from u j to u j-1 in T 1 ρ i for each i, where 2 ≤ j ≤ k -1. Let X 1,ρ i be the path from u 1 to r in T 1 ρ i for each i. For each u j , 1 ≤ j ≤ k -1, if v is a neighbor of u j and π 0 (v) = 0, then, by the definition of each E( Ĥj,ρ i ), either v or v ++ can be on one of the paths in {X j,ρ 1 , X j,ρ 2 , X j,ρ 3 }. Let v i be the neighbor of u 1 in X 1,ρ i for each i. Since π 0 (r) = 0, by the definition of each E( Ĥ2,ρ i ), either

u k , r + , r , u k , r -, r and u k , r in T 1 ρ 1 , T 1 ρ 2 and T 1 ρ 3 ,
r or r ++ is a vertex in {v 1 , v 2 , v 3 }. If r ∈ {v 1 , v 2 , v 3
}, then we get three pairwise internally disjoint paths u 1 , r , u 1 , r + , r and u 1 , r -, r . Otherwise, we get three pairwise internally disjoint paths u 1 , r ++ , ∆, r , u 1 , r + , r and u 1 , r -, r . Therefore, we get three pairwise internally disjoint paths from u k to r.

Q. E. D. Proof. Similar to the proof of Theorem 3.2.

Q. E. D.

Rooted at Vertices on Higher Layers

The construction of 3-ISTs rooted at r, 2 ≤ l(r) ≤ n, has two stages: Backbone Establishment

Stage and Branching Stage. In Backbone Establishment Stage, we shall first define subgraphs on every cluster S k that contains an ancestor of r. Then dedicated layer edges of P n are selected for connecting subgraphs of S k and S k-1 , for each k = 1, 2, . . . , l(r), to establish tree backbones. We further do an expansion on tree backbones to build 3-ISTs of P n rooted at r in Branching Stage.

The detailed description of the two stages are given in the following two subsections.

Backbone Establishment Stage

A block is an a-block if it contains an ancestor of r (including r). Let A k denote the a-block on layer k of P n , where 1 ≤ k ≤ l(r). Let S k be the cluster containing an a-block on layer k and BB r be the subgraph induced by the vertex set

l(r) k=0 V (S k ). A block B of BB r is said to be a b-block if B is not an a-block. Every vertex of an a-block (respectively, a b-block) is called an a-vertex
(respectively, a b-vertex). The corner vertex and inner vertex of A k are denoted as a k,0 and a k,3 , respectively, and a + k,0 and a - k,0 are also denoted by a k,1 and a k,2 , respectively. Every V (S k ) can be partitioned into four vertex subsets

U k,0 , U k,1 , U k,2 and U k,3 . Let U k,0 = { a k,0 , a +3 k,0 , a +6 k,0 , a +9 k,0 }, U k,1 = { a +1 k,0 , a +2 k,0 , a +5 k,0 , a +8 k,0 }, U k,2 = { a +11 k,0 , a +10 k,0 , a +7 k,0 , a +4 k,0 } and U k,3 = { a k,3 , a -1 k,3 , a -2 k,3
, a -3 k,3 } . Notice that every U k,i contains exactly one vertex of each block of BB r .

Let π 1 : V → {0, 1, 2, 3} be a coloring on BB r , where for each vertex v ∈ V (BB r ), π 1 (v) ∈ {0, 1, 2, 3}. For an S k , 2 ≤ k ≤ l(r) -1, if A k is the top-left block or top-right block of S k , we assign color i to every vertex of U k,i . Otherwise, we assign colors 0, 2, 1 and 3 to every vertex of U k,0 , U k,1 , U k,2 and U k,3 , respectively. According to the above coloring rules for π 1 , we get colorings Π 0 , Π 1 , Π 2 and Π 3 for a cluster with respect to an A k locating at the top-left, top-right, bottom-left and bottom-right block of S k , respectively. Figure 3 depicts the four possible π 1 colorings Π 0 , Π 1 , Π 2 and Π 3 of a cluster S k . The block having grey vertices along with bold edges indicates an a-block.

Let h k,i , i = 0, 1, 2, 3, denote the a-vertex of color i in A k and h k = {h k,1 , h k,2 , h k,3 }. The coloring of S 1 is the same as the coloring of A 2 . That is, if v is the corner vertex of A 2 , then we assign colors π 1 (v), π 1 (v + ), π 1 (v -) and π 1 (v ++ ) to p(v), p(v) + , p(v) -and p(v) ++ , respectively. The π 1 coloring of S l(r) is treated as a special case of π 1 and determined by the π 1 coloring of A l(r)-1 in RootColoring Algorithm.

Input: π 1 coloring of A l(r)-1 .

Output: π 1 coloring of S l(r) . begin Assign color 0 to all vertices of U l(r),0 ;

Case π 1 (p(r)) ∈ {0, 3}. Assign color 3 to all vertices of U l(r),3 ; If π 1 (p(r) + ) = 1, then assign color 1 to all vertices of U l(r),1 and color 2 to U l(r),2 else assign color 2 to every vertex of U l(r),1 and color 1 to U l(r),2 ;

Case π 1 (p(r)) = 1.

Assign color 1 to all vertices of U l(r),3 ; If π 1 (p(r) + ) = 0, then assign color 2 to all vertices of U l(r),1 and color 3 to U l(r),2 else assign color 3 to every vertex of U l(r),1 and color 2 to U l(r),2 ;

Case π 1 (p(r)) = 2. Assign color 2 to all vertices of U l(r),3 ; If π 1 (p(r) + ) = 0, then assign color 1 to all vertices of U l(r),1 and color 3 to U l(r),2 else assign color 3 to every vertex of U l(r),1 and color 1 to U l(r),2 ;

Adjust the coloring of A l(r) : Assign color π 1 (r ++ ) to a l(r),0 , and then assign color π 1 (r) to r ++ ; Assign color 0 to r; end

RootColoring Algorithm

We are able to establish three tree backbones T B r,i on BB r for each i = 1, 2, 3. Each T B r,i is regarded as an l(r)-layered graph. For a v ∈ V (BB r ), let c i (v) denote the child of v of color i. Let H k,i denote a subgraph of an S k , where 1 ≤ k ≤ l(r) and 1

≤ i ≤ 3. Let V (H 1,i ) = {h 1,0 , h 1,1 , h 1,2 , h 1,3 , ∆} and E(H 1,i ) = {(h 1,i , ∆)}. We define two o-paths P k,ρ 1 = a k,1 , a +1 k,1 , a +2 k,1 , . . . , a +9 k,1 , P k,ρ 2 = a k,2 , a -1 k,2 , a -2 k,2 , . . . , a -9 k,2 and an i-path P k,ρ 3 = a k,3 , a -1 k,3 , a -2 k,3 , a -3 k,3
for every S k . For convenience, let a 1 , a 2 and a 3 denote as a +1 l(r),1 , a -1 l(r),2 and a -1 l(r),3 , respectively, and let ρ i = π 1 (a i ) for each i. The three subgraphs H k,ρ 1 , H k,ρ 2 and H k,ρ 3 of S k are defined in the following:

E(H k,ρ j ) = E(P k,ρ j ) ∪ {(u, v) ∈ E(S k )|u ∈ V (A k ), π 1 (u) = ρ 3 and π 1 (v) = ρ j } ∪ {(v, p(v))|v ∈ V (A l(r)
) and π 1 (v) = ρ j } for j = 1, 2, and

E(H k,ρ 3 ) = E(P k,ρ 3 ) ∪ {(u, v) ∈ E(S k )|u ∈ V (A k ), π 1 (u) = ρ 3 and π 1 (v) = ρ 1 or ρ 2 } ∪{(v, p(v))|v ∈ V (A l(r) ) and π 1 (v) = ρ 3 } ∪ {(v, p(v))|v ∈ V (A k ) and π 1 (v) = 0}.
Among the four a-vertices of an A k , 2 ≤ k ≤ l(r) -1, h k,ρ i is adjacent to a b-vertex of H k,ρ i and its parent, while the other three a-vertices are isolated in H k,ρ i . For connectivity, every a-vertex of H k,ρ i is incident to a child of color ρ i in H k+1,ρ i . Figure 4 illustrates subgraphs H k,ρ 1 , H k,ρ 2 and H k,ρ 3 of S k . Bold edges are edges of subgraphs H k,ρ i , 1 ≤ i ≤ 3, and grey vertices are a-vertices.

Let E 1 = E( r + , r ++ , r -, r ) ∪ {(r -, p(r))}, E 2 = E( r -, r ++ , r + , r ) ∪ {(r + , p(r))} and E 3 = {(v, p(r))|v ∈ V (A l(r) )}. For each T B r,i , let R i denote the subgraph with the vertex set V (A l(r) ) ∪ {p(r)} and an edge set in {E 1 , E 2 , E 3 }, where i = 1, 2, 3. The formal definition of each T B r,i is in the following:

Definition 3.1.

(1)

E(R π 1 (r -) ) = E 1 , E(R π 1 (r + ) ) = E 2 and E(R π 1 (r ++ ) ) = E 3 . (2) V (T B r,ρ i ) = V (BB r ), E(T B r,ρ i ) = E(H 1,ρ i ) ∪ E(R ρ i ) l(r) k=2 2 k-2 -1 a,b=0 E(H ρ i (k; a, b))
, where ρ i = π 1 (a i ) and i = 1, 2, 3.

Lemma 3.3. The graphs T B 1 , T B 2 and T B 3 are spanning trees of BB r rooted at r.

Proof. Since E(H 1,i ) = {(h 1,i , ∆)}, 1 ≤ i ≤ 3, every H 1,i is clearly acyclic. Since each H k,i , k = 2, 3, . . . , l(r) -1
, is constructed as a tree along with three isolated a-vertices on S k , every H k,i is acyclic. In the S l(r) , A l(r) and p(r) form three tree subgraphs R 1 , R 2 and R 3 , and the remaining three b-blocks form tree subgraphs H l(r),1 , H l(r),2 and H l(r),3 . In addition, H l(r),i and R i share a common a-vertex u ∈ {a l(r),1 , a l(r),2 , a l(r),3 }. For connectivity, each vertex v ∈ V (A l(r) ) of color i in H k,i has an edge (v, p(v)) ∈ E(H k,i ) for connecting subgraphs H k,i and H k-1,i , where k = 2, 3, . . . , l(r) and each p(v) is in fact an a-vertex of H k-1,i . Thus, T B r,i is a tree. Actually, each T B r,i is a spanning tree because V (T B r,i ) = V (BB r ).

Q. E. D.

For convenience, let u j be the dummy vertex with dummy edges incident to every vertex of h j for j = 1, 2, . . . , l(r) -1 and u l(r) be the dummy vertex with dummy edges incident to a 1 , a 2 and a 3 in the remaining text of this section.

Lemma 3.4. The paths from u k-1 to u k in each T B r,i are pairwise internally disjoint, where

1 ≤ i ≤ 3 and 2 ≤ k ≤ l(r) -1.
Proof. Let a +1 k,0 and a +11 k,0 be h k,ρ 1 and h k,ρ 2 , respectively. Let P ρ i be the path from We first consider the case when k = 2. By the definition of the π 1 coloring, the coloring of S 1 is the same as the coloring of A 2 . So, a +2 k,0 = c ρ 1 (h 1,ρ 1 ) and a +10 k,0 = c ρ 2 (h 1,ρ 2 ). Thus, we get disjoint

c ρ i (h k-1,ρ i ) to h k,ρ i in H k,ρ i for i = 1, 2, 3. Since c ρ i (h k-1,ρ i ) ∈ V (P k,ρ i ), P ρ i is
paths P ρ 1 = a +2 k,0 , a +1 k,0 and P ρ 2 = a +10 k,0 , a +11 k,0 . For the case 3 ≤ k ≤ l(r) -1, if c ρ 1 (h k-1,ρ 1 ) is an a-vertex, P ρ 1 = h k,ρ 1 . By the definition of H k,ρ 2 , h k,ρ 1 ∈ V (H k,ρ 2 ). That is, h k,ρ 1 ∈ V (P ρ 2 ).
Thus, P ρ 1 P ρ 2 . Due to the same reason, P ρ 1 and P ρ 2 are disjoint for the case that c ρ 2 (h k-1,ρ 2 ) is an a-vertex. Consider the case that both c ρ 1 (h k-1,ρ 1 ) and c ρ 1 (h k-1,ρ 2 ) are b-vertices. Since h k-1,ρ 1 and

h k-1,ρ 2 are not adjacent, C B (h k-1,ρ 1 ) and C B (h k-1,ρ 2 ) must be two non-adjacent b-blocks of S k . So, C B (h k-1,ρ 1 ) is either A - k or A + k . Case 1. C B (h k-1,ρ 1 ) = A - k .
We first assume that A k is the top-left block of S k . Then C B (h k-1,ρ 1 ) is the bottom-left block of S k and hence h k-1,ρ 1 is the bottom-left vertex of A k-1 . Based on the coloring rules of π 1 , every vertex of

U k,i is assigned the color number i when A k is the top-left block of S k . So, π 1 (h k,ρ 1 ) = π 1 (a +1 k,0 ) = 1.
Then ρ 1 = 1 and π 1 (h k-1,ρ 1 ) = 1. However, every bottom-left vertex of an a-block must be of color 0 (in Π 2 ), 3 (in Π 1 ) or 2 (in Π 0 and Π 3 ) which contradicts the fact that h k-1,ρ 1 is the bottomleft vertex of A k-1 . This implies that A k can not be the top-left block of S k . Due to the same reason, contradiction occurs on the condition that A k is the top-right block, bottom-left block or bottom-right block of S k .

Case 2. C

B (h k-1,ρ 1 ) = A + k .
Since, by the definition of

U k,1 , π 1 (a +1 k,0 ) = π 1 (a +2 k,0 ), it follows that a +2 k,0 is the unique vertex of color ρ 1 in C B (h k-1,ρ 1
) and hence c ρ 1 (h k-1,ρ 1 ) must be a +2 k,0 . So, P ρ 1 = a +2 k,0 , a +1 k,0 . We also get

P ρ 2 = a +10 k,0 , a +11 k,0
because both a +10 k,0 and a +11 k,0 are in U k,2 and are of the same color. Therefore,

P ρ 1 P ρ 2 . Q. E. D.
For any vertex v of BB r , we want to show the paths from v to r in T B 1 , T B 2 and T B 3 are pairwise internally disjoint. Each path from v to r in a T B r,i , 1 ≤ i ≤ 3, can be regarded as a concatenation of three subpaths, including the subpath from v to its nearest a-vertex h k,i , l(v) ≤ l(k) (see Lemma 3.5), the subpath from h k,i to h l(r)-1,i (see Lemma 3.3), the subpath from h l(r)-1,i to a vertex a of A l(r)

(see Corollaries 3.1 and 3.2) and the subpath from a to r (see Lemma 3.7). We are ready to give proofs for the above subpaths.

Lemma 3.5. If u k is a b-vertex of S k , 2 ≤ k ≤ l(r) -1, then the paths from u k to u k in each T B r,i , i = 1, 2, 3, are pairwise internally disjoint.
Proof. Let a +1 k,0 and a +11 k,0 be h k,ρ 1 and h k,ρ 2 , respectively. Since each T B r,ρ i , i = 1, 2, 3, by Lemma 3.3, is a spanning tree of BB r , we have the path P ρ i from u k to h k,ρ i in T B r,ρ i for each i.

We first prove V (P ρ 3 ) ∩ V (P ρ j ) = {u k }, where j = 1, 2. If u k is a corner vertex, then π 1 (u k ) = 0 and

u ++ k is an inner vertex of color ρ 3 . By the definition of H k,ρ 3 , (u k , p(u k )), (u ++ k , p(u k )) ∈ E(H k,ρ 3 ). Thus, u k , p(u k ), u ++ k is a subpath of P ρ 3 . Since u ++ k ∈ V (P k,ρ 3 ), P ρ 3 -u k -p(u k ) is a subpath of P k,ρ 3 . In contrast, P ρ j is a subpath of P k,ρ j because u k ∈ V (P k,ρ j ). Moreover, since p(u k ) ∈ V (P k,ρ j ) and P k,ρ 3 P k,ρ j , V (P ρ 3 ) ∩ V (P ρ j ) = {u k }.
Otherwise, u k is either an inner vertex or adjacent to an inner vertex. Then P ρ j -u k and P ρ 3 -u k are subpaths of P k,ρ j and P k,ρ 3 , respectively. Therefore,

V (P ρ 3 ) ∩ V (P ρ j ) = {u k }. It remains to prove V (P ρ 1 ) ∩ V (P ρ 2 ) = {u k }. Case 1. u k is an outer vertex. Let u k = a +d k,0 , where 2 ≤ d ≤ 10. Since h k,ρ 1 = a +1 k,0 and h k,ρ 2 = a +11 k,0 , P ρ 1 = a +d k,0 , a +(d-1) k,0 , • • • , a +1 k,0 and P ρ 2 = a +d k,0 , a +(d+1) k,0 , • • • , a +11 k,0 . Clearly, V (P ρ 1 ) ∩ V (P ρ 2 ) = {u k }. Case 2. u k is an inner vertex.
Every inner vertex is of color ρ 3 and has neighbors a +d k,0 (∈ U k,1 ) and a

+(d+2) k,0 (∈ U k,2 ) of
+(d+2) k,0 ) ∈ E(H k,ρ 2 ). Then paths P ρ 1 = u k , a +d k,0 , a +(d-1) k,0 , • • • , a +1 k,0 and P ρ 2 = u k , a +(d+2) k,0 , a +(d+3) k,0 , • • • , a +11 k,0 share the common vertex u k . Q. E. D.
The next result follows immediately.

Corollary 3.1. If u l(r) is a b-vertex of S l(r) , then the paths from u l(r) to u l(r) in each T B r,i , i = 1, 2, 3, are pairwise internally disjoint. Lemma 3.6. If u k is an a-vertex of S k , 1 ≤ k ≤ l(r) -2, then the paths from u k to u k+1 in each T B r,i , i = 1, 2, 3, are pairwise internally disjoint.
Proof. Let a +1 k+1,0 and a +11 k+1,0 be h k+1,ρ 1 and h k+1,ρ 2 , respectively. Let B be the block containing

c ρ i (u k ) for i = 1, 2, 3. By the definition of E(H k+1,ρ i ), the edge (u k , c ρ i (u k )) ∈ E(H k+1,ρ i ) for each i. If B is an a-block, paths u k , c ρ i (u k ), u k+1 in T B r,ρ i , for i = 1, 2, 3, are pairwise internally disjoint.
For the case B is a b-block, let P ρ i be the path from

c ρ i (u k ) to h k+1,ρ i in H k+1,ρ i . Since c ρ i (u k ) ∈
V (P k+1,ρ i ), P ρ i is a subpath of P k+1,ρ i . Recall that P k+1,ρ 3 is an i-path, whereas both P k+1,ρ 1 and P k+1,ρ 2 are o-paths. Thus, P ρ 3 P ρ 1 and P ρ 3 P ρ 2 . It remains to prove

P ρ 1 P ρ 2 . Since c ρ 1 (u k ) ∈ U k+1,1 and c ρ 2 (u k ) ∈ U k+1,2
, we let a +d k+1,0 and a

+(d+2)
k+1,0 be c ρ 1 (u k ) and c ρ 2 (u k ), respectively, where d ∈ {2, 5, 8}. Then paths P ρ 1 = a +d k+1,0 , a

+(d-1) k+1,0 , • • • , a +1 k+1,0 and P ρ 2 = a +(d+2)
k+1,0 , a

+(d+3) k+1,0 , • • • , a +11 k+1,0 are disjoint. Q. E. D. Corollary 3.2. If u l(r)-1 is an a-vertex of S l(r)-1
, then the paths from u l(r)-1 to u l(r) in each T B r,i , i = 1, 2, 3, are pairwise internally disjoint.

Lemma 3.7. The paths from u l(r) to r in each T B r,i , for i = 1, 2, 3, are pairwise internally disjoint.

Proof. Let π 1 (a i ) = ρ i for i = 1, 2, 3. Recall that (a l(r),i , a i ) ∈ E(H l(r),ρ i ). Let P ρ i ⊆ R ρ i be
the path from a l(r),i to r in T B r,ρ i for each i.

Case 1. r is a l(r),1 .

Intuitively, P ρ 1 = r . Vertices r + , r -and r ++ are a l(r),3 , a l(r),0 and a l(r),2 , respectively. Since

π 1 (r + ) = ρ 3 and E(R π 1 (r + ) ) = E 2 , E(R ρ 3 ) = E 2 .
Then P ρ 3 = r + , r reveals the fact that P ρ 3 ⊆ R ρ 3 . Recall that we assign color π 1 (r ++ ) to a l(r),0 in RootColoring Algorithm. So π 1 (r -) = ρ 2 .

Furthermore, since

E(R π 1 (r -) ) = E 1 , it follows that E(R ρ 2 ) = E 1 .
Then, P ρ 2 = r ++ , r -, r due to

P ρ 2 ⊆ R ρ 2 .
Clearly, P ρ 1 , P ρ 2 and P ρ 3 are pairwise internally disjoint.

Case 2. r ∈ {a l(r),0 , a l(r),2 , a l(r),3 }.

Similar to the proof of Case 1.

Q. E. D.

Lemma 3.8. The paths from u k to r in each T B r,i are pairwise internally disjoint, where 1 ≤ k ≤ l(r) -1 and 1 ≤ i ≤ 3.

Proof. Let ρ i = π 1 (a i ) for i = 1, 2, 3. By Lemma 3.4, we have pairwise internally disjoint paths

X j-1,ρ i from u j-1 to u j , where 1 ≤ i ≤ 3, k + 1 ≤ j ≤ l(r) -1 and h j-1,ρ i , h j,ρ i ∈ V (X j-1,ρ i ).
For each i, let X l(r)-1,ρ i be the path from u l(r)-1 to u l(r) and let X l(r),ρ i be the path from u l(r) to r in

T B r,ρ i . Let Y l(r)-1,ρ i be the subpath of X l(r)-1,ρ i from h l(r)-1,ρ i to a i in T B r,ρ i for each i. Notably, h l(r)-1,ρ i 1 , a i 1 ∈ V (X l(r)-1,ρ i 2 ) if i 1 = i 2 .
We shall list pairwise internally disjoint paths from u l(r)-1

to r in each T B r,ρ i to complete the proof.

Case 1. π 1 (p(r)) = 0.

From RootColoring Algorithm, every vertex of U l(r),1 , U l(r),2 and U l(r),3 is assigned the color π 1 (p(r) + ), π 1 (p(r) -) and π 1 (p(r) ++ ), respectively. So, π 1 (a 1 ) = π 1 (p(r) + ), π 1 (a 2 ) = π 1 (p(r) -) and π 1 (a 3 ) = π 1 (p(r) ++ ), implying p(r) + , p(r) -and p(r) ++ are h l(r)-1,ρ 1 ,h l(r)-1,ρ 2 and h l(r)-1,ρ 3 , respec-

tively. Since c ρ 1 (h l(r)-1,ρ 1 ) = a 1 and c ρ 2 (h l(r)-1,ρ 2 ) = a 2 , it follows that Y l(r)-1,ρ 1 = h l(r)-1,ρ 1 , a 1 and Y l(r)-1,ρ 2 = h l(r)-1,ρ 2 , a 2 . Since h l(r)-1,ρ 1 , h l(r)-1,ρ 2 , a 1 , a 2 ∈ V (Y l(r)-1,ρ 3 ), Y l(r)-1,ρ 1 , Y l(r)-1,ρ 2
and Y l(r)-1,ρ 3 are pairwise disjoint. Moreover, by Lemma 3.7, we have pairwise internally disjoint paths X l(r),ρ i from u l(r) to r, where 1 ≤ i ≤ 3 and a i ∈ V (X l(r),ρ i ).

Case 2. π 1 (p(r)) = 1.

Vertex p(r) is h l(r)-1,1 . By the definition of R 1 , the path from p(r) to r in T B r,1 , denoted P 1 , is a subgraph of R 1 . From RootColoring Algorithm, every vertex of U l(r),3 is assigned color 1. If π 1 (p(r) + ) = 0, every vertex of U l(r),1 and U l(r),2 is assigned color 2 and 3, respectively. So, p(r) - and p(r) ++ are h l(r)-1,3 and h l(r)-1,2 , respectively. Then Y l(r)-1,3 = p(r) -, a 2 . Since p(r) -, a 2 ∈ V (Y l(r)-1,ρ 3 ), Y l(r)-1,2 and Y l(r)-1,3 are disjoint. By Lemma 3.7, we have internally disjoint paths X l(r),i 2 from u l(r) to r, where i 2 = 2, 3 and a i 2 ∈ V (X l(r),i 2 ). Notably, each X l(r),i 2 is a subgraph of R i 2 and shares a unique common vertex r with P 1 . For the case π 1 (p(r) + ) = 3, due to the same reason, we get pairwise internally disjoint paths from u l(r)-1 to r in each T B r,i .

Case 3. π 1 (p(r)) ∈ {2, 3}.

Similar to the proof of Case 2.

Q. E. D.

Theorem 3.5. For a given root vertex r, 2 ≤ l(r) ≤ n, in P n , BB r has 3-ISTs.

Proof. Let ρ i = π 1 (a i ) for i = 1, 2, 3. Let v ∈ V (BB r ). By Lemma 3.3, we have paths P ρ i from v to r in T B r,ρ i for each i. We want to show P ρ 1 , P ρ 2 and P ρ 3 are pairwise internally disjoint.

Case 1. l(v) = 0.

Vertex v is ∆ and adjacent to every vertex of h 1 . By Lemma 3.4, we have pairwise internally disjoint paths X 1,ρ i from v to u 2 , where 1 ≤ i ≤ 3 and h 1,ρ i , h 2,ρ i ∈ V (X 1,ρ i ). Furthermore, by Lemma 3.8, we have pairwise internally disjoint paths X 2,ρ i from u 2 to r, where 1

≤ i ≤ 3 and h 2,ρ i , a i ∈ V (X 2,ρ i ). Let Y 1,ρ i = X 1,ρ i -u 2 and Y 2,ρ i = X 2,ρ i -u 2 for each i. Clearly, paths Y 1,ρ i Y 2,ρ i from v to r are pairwise internally disjoint for i = 1, 2, 3.
Case 2. v is an a-vertex and 1 ≤ l(v) ≤ l(r) -2.

By Lemma 3.6, we have pairwise internally disjoint paths X 1,ρ i from v to u l(v)+1 in each T B r,ρ i , where 1 ≤ i ≤ 3 and h l(v)+1,ρ i ∈ V (X 1,ρ i ). Furthermore, by Lemma 3.8, we have pairwise internally disjoint paths X 2,ρ i from u l(v)+1 to r, where 1

≤ i ≤ 3 and h l(v)+1,ρ i ∈ V (X 2,ρ i ). Let Y 1,ρ i = X 1,ρ i -u l(v)+1 and Y 2,ρ i = X 2,ρ i -u l(v)+1 for each i. Clearly, paths Y 1,ρ i Y 2,ρ i from v to r are pairwise internally disjoint for i = 1, 2, 3.
Case 3. v is an a-vertex and l(v) = l(r) -1.

If v = p(r), then, by the definition of each R ρ i , we have three pairwise internally disjoint paths v, r -, r , v, r + , r and v, r . Otherwise, v = p(r). Since c ρ i (v) ∈ V (P k+1,ρ i ), P ρ i is a subpath of P k+1,ρ i . So, P ρ 3 P ρ 1 and P ρ 3 P ρ 2 because P k+1,ρ 3 P k+1,ρ 1 and P k+1,ρ 3 P k+1,ρ 2 . Moreover, since

c ρ 1 (v) ∈ U k+1,1 and c ρ 2 (v) ∈ U k+1,2
belong to the same block, it follows that P ρ 1 P ρ 2 .

Case 4. v is a b-vertex and 2 ≤ l(v) ≤ l(r) -1.

By Lemma 3.5, we have pairwise internally disjoint paths X 1,ρ i from v to u l(v) in T B r,ρ i , where 1 ≤ i ≤ 3 and h l(v),ρ i ∈ V (X 1,ρ i ). Furthermore, by Lemma 3.8, we have pairwise internally disjoint paths X 2,ρ i , from u l(v) to r, where 1

≤ i ≤ 3 and h l(v),ρ i , a i ∈ V (X 2,ρ i ). Let Y 1,ρ i = X 1,ρ i -u l(v) and Y 2,ρ i = X 2,ρ i -u l(v) for each i. Clearly, paths Y 1,ρ i Y 2,ρ i from v to r are pairwise internally disjoint for i = 1, 2, 3. Case 5. v ∈ V (A l(r) ).
The case v = r is trivial. For cases v ∈ {r + , r -, r ++ }, we shall list three pairwise internally disjoint paths for each case, where each path is a subpath of R ρ i . If v = r + , we have paths r + , r ++ , r -, r , r + , r and r + , p(r + ), r . For the case v = r -, we have r -, r , r -, r ++ , r + , r and r -, p(r -), r .

And we have r ++ , r -, r , r ++ , r + , r and r ++ , p(r ++ ), r for the case v = r ++ . Case 6. v ∈ V (S l(r) ) \ V (A l(r) ).

By Corollary 3.1, we get pairwise internally disjoint paths X 1,ρ i from v to u l(r) in T B r,ρ i , where 1 ≤ i ≤ 3 and a i ∈ V (X 1,ρ i ). Furthermore, by Lemma 3.7, we have pairwise internally disjoint paths X 2,ρ i from u l(r) to r, where 1 ≤ i ≤ 3 and a

i ∈ V (X 2,ρ i ). Let Y 1,ρ i = X 1,ρ i -u l(r) and Y 2,ρ i = X 2,ρ i -u l(
(T B r,i ) v∈V (A l(r) )∪V b E(T i (v)). Lemma 3.9. Let v ∈ V (A l(r) ) ∪ V b . If u k is a vertex of S k in P n (p(v)), 2 ≤ k ≤ n -l(v) + 1, then
the paths from u k to r in each T 2 r,i , for i = 1, 2, 3, are pairwise internally disjoint.

Proof. S 1 is either A l(r) or a b-block of BB r . If S 1 = A l(r) , then, by Theorem 3.3, we have pairwise internally disjoint paths from u k to r in each T 2 r,i . Otherwise, S 1 is a b-block of BB r . Let u j be the dummy vertex with dummy edges incident to every vertex of P B (S j+1 ) for j = 1, 2, . . . , k -1.

Let u l(r) be the dummy vertex with dummy edges incident to every vertex of {a 1 , a 2 , a 3 }. Let ρ i = π 1 (a i ) for each i. From Lemma 3.1, we get pairwise internally disjoint paths X k,ρ i from u k to u k-1 in T ρ i (v) for each i = 1, 2, 3. By applying Lemma 3.2, we get pairwise internally disjoint paths X j,ρ i from u j to u j-1 in T ρ i (v) for each i, where 2

≤ j ≤ k -1. Let Y k,ρ i = X k,ρ i -u k-1 and
Y j,ρ i = X j,ρ i -u j -u j-1 for each i, j. We now list the three pairwise internally disjoint paths Y 1,ρ i from u 1 to r in each T B r,ρ i to complete the proof.

Let V (S 1 ) = {v 0 , v ρ 1 , v ρ 2 , v ρ 3 } such that π 1 (v 0 ) = 0 and π 1 (v ρ i ) = ρ i for i = 1, 2, 3. Recall that v ρ 3 = v ++ 0 .
By the definition of each E( Ĥ2,ρ i ), either v ρ 3 or v 0 can be on the path X 2,ρ 3 .

Case 1. S 1 is a b-block of S l(r) .

By Lemma 3.7, we have pairwise internally disjoint paths Z 1,ρ i from u l(r) to r in T B r,ρ i , where 1 ≤ i ≤ 3 and a i ∈ V (Z 1,ρ i ). Furthermore, from Corollary 3.2, we get pairwise internally disjoint paths P ρ i from p(v) to u l(r) in T B r,ρ i , where 1 ≤ i ≤ 3 and a i ∈ V (P ρ i ). Since (v ρ i , p(v)) ∈ E(T B r,ρ i ),

P ρ i -p(r) is the path from v ρ i to u l(r) in T B r,ρ i . If v ρ 3 ∈ V (X 2,ρ 3 ), we get paths Y 1,ρ i = Z 2,ρ i Z 1,ρ i - u l(r) for each i. Otherwise v 0 ∈ V (X 2,ρ 3 ). Since v 0 , p(v 0 ), v ρ 3 is a subgraph of E(H l(r),ρ 3 ), we get the path Y 1,ρ 3 = v 0 , p(v 0 ), v ρ 3 Z 2,ρ 3 Z 1,ρ 3 -u l(r) . In addition, Y 1,ρ 1 = Z 2,ρ 1 Z 1,ρ 1 -u l(r) and Y 1,ρ 2 = Z 2,ρ 2 Z 1,ρ 2 -u l(r) .
Case 2. S 1 is not a block of S l(r) .

Notice that S 1 is a b-block and l(v) < l(r). By Lemma 3.8, we have pairwise internally disjoint paths Z 1,ρ i from u l(v) to r in T B r,ρ i , where 1 ≤ i ≤ 3 and h l(v),ρ i ∈ V (Z 1,ρ i ). Furthermore, from Lemma 3.6, we get pairwise internally disjoint paths Q. E. D.

P ρ i from p(v) to u l(v) in T B r,ρ i , where 1 ≤ i ≤ 3 and h l(v),ρ i ∈ V (P ρ i ). Since (v ρ i , p(v)) ∈ E(T B r,ρ i ), P ρ i -p(r) is the path from v ρ i to u l(v) in T B r,ρ i . If v ρ 3 ∈ V (X 2,ρ 3 ), we get paths Y 1,ρ i = Z 2,ρ i Z 1,ρ i -u l(v) for each i. Otherwise v 0 ∈ V (X 2,ρ 3 ). Since v 0 , p(v 0 ), v ρ 3 is a subgraph of E(H l(v),ρ 3 ), we get the path Y 1,ρ 3 = v 0 , p(v 0 ), v ρ 3 Z 2,ρ 3 Z 1,ρ 3 -u l(v) . In addition, Y 1,ρ 1 = Z 2,ρ 1 Z 1,ρ 1 -u l(v) and Y 1,ρ 2 = Z 2,ρ 2 Z 1,ρ 2 -u l(v) . It concludes that paths Y k,ρ i Y k-1,ρ i . . . Y 1,ρ i from u k to r in T 2 r,ρ i , for i = 1,

Conclusion Remarks

In this paper, we present linear time algorithms to construct 3-ISTs in an n-dimensional pyramid P n . To the best of our knowledge, this is the first result for constructing ISTs in P n . The tree height and the average distance of an IST are considered as two performance metrics in our algorithms.

The height of a tree T is the the number of vertices in a longest path from the root to a leaf. The average distance of T is the average of all distances from any vertex to the root. The resulting values are shown in Table 1. In Table 1, the column "height" provides an upper bound to the values of the average distance of a tree, where n is the dimension of the given network. Columns 4-10 demonstrate average distances for different network scales. The data are calculated on different scenarios to see the tree heights and the average distances for different scales of pyramid networks.

Although the values of average distances are associated with a proportional increase in the dimension of the networks, the resulting values of T 0 ρ i , T 1 ρ i and T 2 r,ρ i are still bounded by 2.81n, 2.81n and 6.54n, respectively, even when the given network is of order over 1 million vertices. ≤ 5.48n +4l(r) + ε ε: the distance from an a-vertex of S l(r) to r.

2

 2 and π 0 (x ++ ) = ρ 3 . We assign color π 0 (x + ) to the corner vertex of C B (x + ), to the two outer vertices incident to C B (x + ), and to the outer vertex incident to C B (x) in C B (x -) (see Statement 2 of HFinding Algorithm). Statement 3 assigns color π 0 (x -) to the corner vertex of C B (x -), to the two outer vertices incident to C B (x -), and to the outer vertex incident to C B (x ++ ) in C B (x + ). In Statement 4, we assign color π 0 (x ++ ) to each inner vertex of S k . The remaining uncolored vertices of S k are assigned color 0 in Statement 5.

  respectively, from u k to r. The case u k = r is trivial. Consider the case k = 1 and u k = r. If u k = r ++ , then paths u k , r + , r , u k , r -, r and u k , p(r), r are in T 1 ρ 1 , T 1 ρ 2 and T 1 ρ 3 , respectively, and are pairwise internally disjoint. Similarly we have three pairwise internally disjoint paths for the case u k is a neighbor of r and leave the proof to the reader.

Theorem 3 . 4 .

 34 The construction of 3-ISTs of P n rooted at a vertex on layer 1 can be solved in O(|V |) time, where |V | is the number of vertices of P n .

Theorem 3 . 6 .

 36 The construction of 3-ISTs of P n rooted at r, 2 ≤ l(r) ≤ n, can be solved in O(|V |) time, where |V | is the number of vertices of P n . Proof. The construction of 3-ISTs rooted at r, 2 ≤ l(r) ≤ n, contains the Backbone Establishment Stage and the Branching Stage. Let r = (k; x, y). In the Backbone Establishment Stage, every vertex (k -j; x 2 j , y 2 j ), for j = 0, 1, . . . , k -1, is an ancestor of r and can be decided in O(1) time, implying every a-block can be found in O(1) time. Since every cluster of BB r can be colored by constant time, π 1 coloring costs O(|V (BB r )|) time. We then need additional constant time to have an RootColoring Algorithm. Vertices of h k of a cluster are decided in constant time and hence every H k,i is established in constant time. Since each edge set E(H x,i ), i = 1, 2, 3 has |V (BB r )| -1 edges and each edge of E(H x,i ) can be checked in constant time, the finding of E(H x,i ) costs O(|V (BB r )|) time. Therefore, Backbone Establishment Stage costs O(|V (BB r )|) time. In Branching Stage, every flat subpyramid P n (p(v)) needs O(|V (P n (p(v)))|) time π 0 coloring. By Theorem 3.2, the construction of 3-ISTs of every P n (p(v)) rooted at p(v) can be solved in O(|V (P n (p(v)))|) time, where v ∈ V (A l(r) ) ∪ V b . The overall time complexity of Branching Stage is O(|V (P n -BB r )|). That is, the construction of 3-ISTs of P n rooted at r, can be solved in O(|V (P n )|) time.

Figure 1 :

 1 Figure 1: A top view of the pyramid P 2 .

Figure 2 :

 2 Figure 2: The bold cluster edges establish three subgraphs (a) Ĥk,ρ 1 , (b) Ĥk,ρ 2 , (c) Ĥk,ρ 3 of a cluster S k , where the parent vertex of the top-left block is of color 0. The dash lines indicate layer edges.

Figure 3 :Figure 4 :

 34 Figure 3: The four possible π 1 colorings Π 0 , Π 1 , Π 2 and Π 3 of a cluster S k when A k is (a) the top-left block; (b) the top-right block; (c) the bottom-left block; (d) the bottom-right block of S k .

  [START_REF] Bao | Reliable broadcasting and secure distributing in channel networks[END_REF] , and every inner vertex of S k has exactly one edge incident to P k,ρ 1 in Ĥk,ρ 1 (See Statement 6). Ĥk,ρ 2 contains the outer path P k,ρ 2 =

	ĥk,ρ 1 , ĥ-5 k,ρ 2 , . . . , ĥ-1 k,ρ 2 , ĥk,ρ 2 , ĥ+1 k,ρ 2 , ĥ+2 k,ρ 2 , . . . , ĥ+5 k,ρ 2 , and every inner vertex has an edge incident to
	P k,ρ 2 (See Statement 7

  k,ρ 1 )) in Ĥk,ρ 3 (SeeStatement 8). For the connectivity of layers, the edge ( ĥk,ρ i , p( ĥk,ρ i )) is used to connect Ĥk,ρ i and Ĥk-1,ρ i , where 1 ≤ i ≤ 3 (See Statements 6-8). It can be seen that P k,ρ 1 , P k,ρ 2 and P k,ρ 3 are pairwise disjoint. Figure2illustrates subgraphs Ĥk,ρ 1 , Ĥk,ρ 2 and Ĥk,ρ 3 of a cluster S k on the condition that the parent vertex of the top-left block of S k is of color 0. The bold edges are edges of subgraphs and the grey vertices represent junction vertices. The formal definitions of Ĥk,ρ 1 , Ĥk,ρ 2 and Ĥk,ρ 3 refer to HFinding Algorithm.

  , . . . , ĥk,ρ 2 in Ĥk,ρ 1 and Ĥk,ρ 2 , respectively.

			k,ρ 1	, . . . , ĥk,ρ 1 and
	ĥ-(6-d) k,ρ 2	,	ĥ-(6-d-1) k,ρ 2

  , . . . , ĥk,ρ 2 in Ĥk,ρ 1 and Ĥk,ρ 2 , respectively.Proof. Let B 1 and B 2 be the block containing ĥk,ρ 1 and ĥk,ρ 2 , respectively. According to the first statement of HFinding Algorithm, both ĥk,ρ 1 and ĥk,ρ 2 are corner vertices and B 1 is in fact

			1 ,	ĥ-(d-1) k,ρ 1	, . . . , ĥk,ρ 1 and
	ĥ+(6-d) k,ρ 2	,	ĥ+(6-d-1) k,ρ 2
	B ++ 2 . Thus, ĥk,ρ 1 = ĥ+6 k,ρ 2 and ĥk,ρ 2 = ĥ+6 k,ρ 1 . Besides, both (2) and (3) immediately follow (1).

  Theorem 3.2. The construction of 3-ISTs of P n rooted at the apex can be solved in O(|V |) time, where |V | is the number of vertices of P n .Proof. At first, we assign color numbers to the four vertices of S 1 and build three subgraphs Ĥ1,i , i = 1, 2, 3, on S 1 in constant time. By using HFinding Algorithm, the coloring of every cluster is determined by the coloring of its parent block and costs constant time. So, the coloring of P n costs O(|V |) time. According to π 0 coloring, ĥk,1 , ĥk,2 and ĥk,3 , k = 2, 3, . . . , n, of S k can be decided in constant time and then every Ĥk,i is established in constant time. Since each edge set

E(T 0 i ), i = 1, 2, 3, has |V | -1 edges and each edge of E(T 0 i ) can be checked in constant time, the finding of E(T 0 i ) costs O(|V |) time. Therefore, the construction of 3-ISTs of P n rooted at the apex is solved in O(|V |) time.

  r) for each i. Clearly, paths Y 1,ρ i Y 2,ρ i from v to r are pairwise internally disjoint (u) is a subgraph of P n by letting a vertex u ∈ V (P n ) be the apex of P n (u). A flat subpyramid P n (u) is a subpyramid without an apex u and a layer 1. Let V b denote the set of b-vertices of BB r . The subgraph P n -BB r is regarded as an union of flat subpyramids, and every flat subpyramid is defined as P n (p(v)), where v ∈ V (A l(r) ) ∪ V b . In particular, P

	for i = 1, 2, 3.
		Q. E. D.
	3.3.2 Branching Stage
	A subpyramid P n n-l(v)+1	2 k-2 -1
	k=2	a,b=0

n (p(v)) is defined to be empty if v ∈ S l(r) and l(r) = n. For easily describing notations in P n (p(v)), we let S k denote the cluster on layer k of P n (p(v)), where 2 ≤ k ≤ n -l(v) + 1. That is, S k is actually a cluster on layer

l(v)+k-1 of P n . For a P n (p(v)), P B (S 2 ) is either A l(r

) or a b-block of BB r , and P B (S 2 ) is also denoted by S 1 . Since S 1 is in fact a block of BB r , S 1 has a π 1 coloring in Backbone Establishment Stage. Henceforth, every cluster of P n (p(v)) can have a π 0 coloring by applying HFinding Algorithm on its parent block. Notations ĥk,i and Ĥk,i , 1 ≤ i ≤ 3, refer to Section 3.1. Let T i (v), 1 ≤ i ≤ 3, denote the spanning subgraph of P n (p(v)) and have the edge set E( Ĥi (k; a, b)). Let T 2 r,i , 1 ≤ i ≤ 3, denote the spanning subgraph of P n with the edge set E

Table 1 :

 1 The table of tree heights and average distances≥ 2 ≤ 9n -19 ≤ 2.50n ≤ 2.60n ≤ 3.35n ≤ 3.99n ≤ 4.47n ≤ 4.83n

	n (dimension)

† This work was supported in part by the Ministry of Science and Technology of the Republic of China under the contract MOST 104-2221-E-034-001.