1.2.1..
. 5. i !

, . . :2 “Ir.
{2. ‘ A A . . V . . . ..a.c:.:.t&&
tar; .x V . V . umwy5.%,:.:.

V
a
Ind.

 

 

 

OI.

kw
‘ndhbr.

flu 143.1 v

..
’ .‘
3....
if? S a:
fiuflfienfi
r if.

'

 

THESIS
t'

i

STATE USNIVER

llllllllllllllllll Ill llllllllllllllllllllll

31293 01564 3368

 

 

 

 

 

 

 

 

 

 

 

 

 

 

This is to certify that the

dissertation entitled

DESIGNING DISTANCE-PRESERVING FAULT-TOLERANT TOPOLOGIES

presented by

SITARAMA SWAMY KOCHERLAKOTA

has been accepted towards fulfillment
of the requirements for

PhD degree in W

 

 

_ 911°...
C ‘ Major pnzqsor
M M/%

Date

 

MS U is an Affirmative Action/Equal Opportunity Institution 0-12771

 

 

LIBRARY
Michigan State
University

 

 

 

PLACE IN RETURN BOX to remove this chockout from your record.

TO AVOID FINES return on or botoro date duo.

    

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MSU to An Afflnnotivo ActioNEquoi Opportunity Instituion
m

 

DESIGNING DISTANCE-PRESERVING FAULT-TOLERANT TOPOLOGIES
By

Sitarama Swamy Kocherlakota

A DISSEERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Computer Science

December 6, 1996

ABSTRACT
DESIGNING DISTANCE-PRESERVING FAULT-TOLERANT TOPOLOGIES
By

S itarama Swamy Kocherlakota

The objective of designing a fault-tolerant communication network (CN) is to maintain its
functionality in the presence of failures. The approaches taken in designing fault-tolerant sys-
tems can be classified, in general, by the functionality criteria. There are two fitnctionality criteria
that have received much attention. First, preserving a topology, which considers a CN functional as
long as a desired topology is contained in the system. Second, preserving a property, which consid-
ers a CN functional as long as a given topological property is satisfied by the underlying topology. In
this dissertation, we study the second functionality criterion. Specifically, designing fault-tolerant
topologies that preserve distance between every pair of non-adjacent nodes in presence of edge

failures.

We introduce and study a new family of fault-tolerant graphs called distance preserving graphs.
A graph G is said to be k-edge distance preserving with respect to a spanning subgraph D, if
there exist It edge-disjoint u-v paths in G of length at most dp(u, v) for every pair of non-adjacent
vertices u, v of D. We present few properties of distance preserving graphs along with a theorem
that characterizes the distance preserving graphs. We study two design models each with a different

optimality criterion. In the first model, minimizing the overall redundancy is considered. The

second model considers regular fault-tolerant topologies with minimum regularity. We present tight
lower and upper bounds for both design models. The focus of this dissertation is on designs based
on the second model. In particular, we construct regular distance preserving graphs with respect
to cycles, crowns, chordal rings, and n-ary 2-cubes. We also prove that the given constructions are
optimal when D = 0p and k S 5.

We also address the issue of the distance between adjacent vertices in D in presence of edge
failures, and show that the distance between adjacent vertices is bounded by a constant. Finally,
given a graph G and a spanning subgraph D, we have showen that there exist a polynomial time
algorithm to determine if G is k-edge distance preserving with respect to D. This study will result in

more cost-effective fault-tolerant systems where distance between communicating nodes is critical.

© Copyright 1996 by Sitarama Swamy Kocherlakota

All Rights Reserved

TABLE OF CONTENTS

LIST OF TABLES vii
LIST OF FIGURES viii
1 Introduction . l
1.1 Functionality Criteria ................................... 3
1.2 Terminology and Notation ................................ 4
1.3 Organization of the Dissertation ............................. 5
2 Measures of Fault Tolerance 6
2.1 Preserving a Desired Topology .............................. 7
2.2 Preserving a Property ................................... 12
2.3 Preserving Connectedness ................................ 13
2.4 Distance .......................................... 15
2.4.1 Preserving Diameter .................................. 15
2.4.2 Preserving Distance ................................... 17
2.5 Proposed Work ...................................... 18
3 Distance Preserving Graphs 20
3.1 Introduction ........................................ 20
3.2 Preliminaries ...................................... ' . 21
3.3 Characterization Result .................................. 21
3.4 Model 1 .......................................... 25
3.4.1 Bounds ......................................... 25
3.5 Model 2 .......................................... 30
3.5.1 Bounds ......................................... 31
3.6 A Bound on the Diameter of G .............................. 35
4 Special Topologies ( 40
4.1 Cycles ........................................... 42
4.2 Crowns .......................................... 48
4.3 Chordal Graphs ...................................... 54
4.4 n-ary 2-cube ........................................ 57
5 An Algorithm To Find 1: Given D and G , 67
5.1 Outline of the Algorithm ................................ g. 68
6 Conclusions 77
6.1 Future Work ........................................ 78

4.1
4.2
4.3
4.4

LIST OF TABLES

k edge—disjoint paths to vertices that are distance 2-away from on. ........... 55
k edge-disjoint paths to vertices that are distance 3-away from v0. .......... ,- 56
k-edge disjoint paths to vertices that distance two away from (i, j) ............ 62
k-edge disjoint paths to vertices that are distance 3 away from (i, j). .......... 66

vi

LIST OF FIGURES

2.1 Taxonomy of topological fault-tolerance ..........................

3.1 G E f3(D) .........................................
3.2 Example: k = 3, dD(w, v) = 2 and dg(u, w) 2 3. ...................
3.3 Graphs G and H are not in f3(D) .............................
3.4 Gopt E f3(D). ......................................
3.5 A complete binary tree of height 2 .............................
3.6 K2 + 75 E .7), (complete binary tree of height 2). ...................
3.7 A 9-order star graph. ...................................
3.8 Case 6(H) = k ...................................... '.
3.9 Case6(H)=k+i .....................................
3.10 Case 1: (11,3) 6 E(G) => (u,v) 6 E(G). ........................
3.11 Case 2: N001.) = N0($) => Na(‘u) = N000). .....................
3.12 K5,5 E .75(K5,5) and diameter Of K5,5 is 2. .......................
3.13 Diameter of K55 — {0, 1} is 3 ...............................

4.1 016- ............................................
4.2 A 5-regular crown of order 16. ............................. '.
4.3 A C(16, 7). ........................................
4.4 A C(16, < 5,7 >). ....................................
4.5 A 8-ary 2-cube. ......................................
4.6 A 3-crown on 12 vertices ..................................
4.7 A set of k edge-disjoint paths between v,- and vg+2 of length 2 in a (k + l)-crown. . . .
4.8 A set of k — 3 edge-disjoint paths of length 3 in a (k + l)-crown .............
4.9 A set of 4 edge-disjoint paths between 120 and v3. ................... ,.
4.10 Vertices that are distance 2 and 3 away from vertex v0. .................
4.11 k edge-disjoint paths between 120 and v,- when 2r — l S j 3 4r — 5 ...........
4.12 k edge-disjoint paths between on and v,- when p - 21' + 1 S j S p — 3. ........
4.13 A set of 3 edge-disjoint paths between on and v7. ....................
4.14 A C(28,7). ........................................
4.15 C(28, < 3, 7,9 >) e f2(C(28, 7)). ...........................
4.16 Edge disjoint paths between 0 and 15 in a C(28, < 3, 7, 9 >) ...............
4.17 Edge disjoint paths between 0 and 19 in a C(28, < 3, 7, 9 >) .............. '.
4.18 0"“cycleand5‘hcycleina8x8torus. .. . . . . . . . . . . . . . . . . . . . . . -. . .
4.19 A 4-crown (k = 3) for the 4‘“ cycle in a 8x8 torus. ...................
4.20 A 4-crown (k = 3) for the 5‘” cycle in a 8x8 torus. ...................
4.21 Vertices that are distance 2 away from (i, j) in n-ary 2-cube. ..............
4.22 Vertices that are distance 3 away from (i, j) in n-ary 2-cube. ..............
4.23 k—edge disjoint paths between (i, j) and (i + 3, j) in a n-ary 2-cube. ..........
4.24 k-edge disjoint paths between (i, j) and (i + 2, j — l) in a n-ary 2-cube .........

vii

8

20
23
24
26
27
27
27
28

32
32
35
36

42
43
43
44
45
45
47
49
5 1

59

viii

4.25 Ic-edge disjoint paths between (i, j) and (i + 1, j — 2) in a n-ary 2-cube ......... 64
4.26 k-edge disjoint paths between (i, j) and (2', j — 3) in a n-ary 2-cube. ......... '. 64
4.27 8-regular graph that belongs to f3(n-ary 2-cube) ..................... 65
5.1 Graphs I and J and their corresponding I ’ and J’ ..................... 69
5.2 Algorithm for finding max k ................................ 72
5.3 Graph H and its G’ ..................................... 72
5.4 Case 1 of the Algorithm. G and the resulting G’. .................... 73
5.5 Case 2 of the Algorithm. G and the resulting G’. .................... 73
5.6 Case 3 of the Algorithm. G and the resulting G’. .................... 73

Chapter 1

Introduction

The necessity for high performance computing Stems from several computationally intensive prob-
lems such as fuel combustion, three dimensional fluid flow, and the design of protein structures, etc
[1]. Many of these computationally intensive problems were discovered in the past two decades.
However, designing systems capable of meeting such high computational requirements has become
increasingly feasible in recent years. This is due to the technological advances in VLSI and paral-
lel processing. In parallel processing, several processors concurrently work on an application with
each processor coordinating with others. This approach is promising for high performance com-
puting because of the enormous amounts of computational power offered by parallel processing
systems [1].

Several architectural approaches have been taken in designing parallel processing systems.
Some of the important considerations in selecting an architecture for a parallel processing system
include simple routing, scalability, cost-effectiveness and reliability [2]. Among the many architec-
tures proposed for parallel processing systems, a particular class of systems called point-to-point
networks has received much attention. The interest in these systems is mainly due to the scalability

and cost-effectiveness [1].

2

Point-to-point networks can be defined as a collection of linked autonomous processors with the
memory partitioned amongst the processors. The memory associated with each processor is local
to that processor and is called local memory. Each processor has direct access to its local mem-
ory; indirect access to the memory located in other processors is facilitated through interprocessor
communication. A processor can communicate with another processor by sending/receiving mes-
sages. These systems are widely known as message passing systems, marked by the nature of their

interprocessor communication.

The processor and link layout of a message passing system is referred to as communication
networks (CN). The underlying topology of a CN is usually modeled by a graph G ( V, E) in which

the vertex set V represents the set of processors and the edge set E represents the links.

One of the main reasons for the interest in CNS is due to their scalability. However, as the
number of components increases, the probability of a failure in the system also increases’. With
failures, the performance of the system may degrade. \Vrth degraded performance, the parallel
algorithm running on the system may no longer be cost-effective to run on a parallel system. In
other words, the application has a low ratio of performance to the resources consumed. Hence, in
designing or selecting a topology for a CN, one fundamental consideration is system-level fault-
tolerance. At this level, the type of faults to be tolerated are processor failures or link failures.
A system is said to be fault-tolerant if it can remain functional in the presence of failures. It is,
however, the topological requirements set by the application environment that essentially determines
when a CN is considered to be functional. In the remaining part of the introduction, we briefly
review the issues and classify the approaches taken in designing fault-tolerant CNS, followed by

notation and the organization of the dissertation.

 

'The rate of the failure probability is dependent on the particular CN under consideration.

1.1 Functionality Criteria

Over the years researchers have considered different approaches in designing fault-tolerant CNS. In
general, these approaches can be classified by the two functionality criteria which have received
much attention. According to one of these criteria, a CN is considered functional as long as a certain
topology is logically contained in the system. In the past few years, much work has been done in
developing parallel algorithms and the best CNS for their executions [3]. For these algorithms, the
existence of certain topologies is a significant factor in delivering the desired performance. Thus, for
such applications, the system should be able to provide (logically) a specific topology throughout
the execution of the algorithm. Designing fault-tolerant systems to guarantee a topology is referred
to as preserving a topology. This criterion was first formulated by Hayes [4], and subsequently a
number of topology preserving designs have been proposed [2, 5, 6, 7, 8, 9, 10, 11].

The second functionality criterion, the focus of this dissertation, considers a CN functional as
long as the underlying topology of the non-faulty system satisfies one or more topological prop-
erties. Designing fault-tolerant systems to guarantee a topological property2 is referred to as pre-
serving a property. The existing work in preserving a property have mainly considered topological
properties involving connectivity or distance. In this criterion, for instance, a CN is functional
as long as there is a non-faulty communication path between each pair of non-faulty processors
[12, 13, 14]. In other words, the underlying topology of a fault-tolerant CN should remain con-
nected in presence of certain failures. Preserving a property is particularly applicable to large-scale
CNS that are to execute concurrent algorithms whose performance is relatively insensitive to in—
frequent changes in system topology [13]. Such algorithms generally permit graceful degradation

by providing the functionality required with degraded performance. In this dissertation, we study

 

2Preserving a topology can also be viewed as a topological property. However, we distinguish these two terms for
clarity.

4

designing “optimal” fault-tolerant CNS that preserve distance between every pair of non-adjacent
nodes and tolerate edge failures. This study will result in more cost-effective fault-tolerant designs

in networks where distance between communicating processors is critical.

1.2 Terminology and Notation

A CN can be modeled as a graph by representing each processor as a vertex and each transmission
link connecting a pair of processors as an edge. In the rest of the dissertation, we do not make a
distinction between the terms “CN” and “graph”. Hence, we use the terms processor (link) and
vertex (edge) interchangeably. In this section, we briefly define the graph theoretic notation used in
this dissertation. Terms not defined here can be found in [15].

All graphs considered here are connected, undirected, without any loops or multiple edges. Let
G(V, E) be a graph with the vertex set V(G) and the edge set E(G). The order and size of the
graph G are |V(G)| and |E(G)|, respectively. Ifan edge e = (u, v) E E(G), then vertices u and
v are said to be adjacent. If F g V(G) (or E(G)) then the graph G -— F represents the subgraph
obtained by removing the vertices (edges) in F from G. If u E V(G) then Na(u) represents the
set of all vertices adjacent to vertex u in G. The set Na(u) is called the neighborhood of u; the
closed neighborhood of u is defined as Nc[u] = Na(u) U {u}. The degree of a vertex u E V(G)
is degg(u) = [Na(u)|. The minimum degree of a graph G is 6(G) = min{degg(u)|u E V(G)}.
The maximum degree of the graph G is A(G) = max{degg(u)|u E V(G)}. If 6(G) = A(G)
= r, then all the vertices of G have the same degree and the graph G is called r-regular; r is
also referred to as the degree of G. The distance dg(u, 1:) between two distinct vertices u and v
in G is defined as the length (in number of edges) of a shortest path joining these vertices. The
complete graph with p vertices is denoted by KP. A complete bipartite graph with m and n

vertices in each partition is denoted by K m.n- 'Ihe complement of a graph G, denoted as G, is a

5
graph with V(G) = V(G) and for every (u,v) ¢ E(G), we have (u,v) E E(G). 'Ihe join of

two graphs G and H, denoted as G + H, is a graph with vertex set V(G) U V(H) and edge set
E(G) U E(H) U {(u, v)| for every u E V(G) and for every v E V(H)}. We denote by C'p acycle

on p vertices, and by Pp a path on p vertices.

1.3 Organization of the Dissertation

In Chapter 2, we present a brief survey of the work to date in designing topology preserving and
property preserving graphs. In Chapter 3, we introduce the distance preserving graphs and present a
theorem that characterizes the distance preserving graphs. We present two design models in design-
ing “optimal” distance preserving graphs in Chapter 3. Also, in Chapter 3, we Show that preserving
the distance between non-adjacent vertices also sets a bound, in presence of edge removal, on the
distance between vertices which were adjacent before any edge removal. Distance preserving graphs
with respect to some special topologies are presented in Chapter 4. An algorithm to find the maxi-
mum value of k given a graph G and a spanning subgraph D is presented in Chapter 5. In Chapter
6, we conclude by outlining the contributions of this dissertation.

In the rest of the dissertation, the terms “fault-tolerance” or “functional” are meaningful in the

context of the criterion under consideration.

Chapter 2

Measures of Fault Tolerance

The degree of fault-tolerance can be quantified either probabilistically or deterministically. Inprob-
abilistic measures, the objective is to find the probability of a system being functional, given the
failure probabilities of its components. To decrease the complexity of the analysis, it is usually
assumed that failures are statistically independent and equiprobable. However, components may
fail, in general, with different probabilities. Probabilistic measures of fault-tolerance seem to model
the real world better than their deterministic counterparts [13]. However, it has been Shown that all
probabilistic measures of reliability which are of practical significance are computationally NP-hard
[16]. Consequently, a number of heuristic algorithms for the computation of these measures have
been proposed.

For deterministic measures researchers have mainly used graph invariants such as connectivity,
diameter, etc. In this dissertation, we focus on designing fault-tolerant CNS and use deterministic

measures to quantify their fault-tolerance.

The Problem

The general question in designing fault-tolerant topologies is:

6

7

“Given a non-negative integer 1:, design a graph G such that after k failures in G,
the remaining graph is still fitnctional ”.

It is often helpful to minimize the cost of the fault-tolerant graph G. This can be achieved by
imposing one or more optimality criteria in designing G. There are three important optimality crite-
ria [17]. The first and second criteria are minimizing the number of vertices and/or minimizing the
number of edges, respectively. Over the years, the above two criteria have received much attention.
In the third optimality criterion, only regular graphs are considered and the objective is to minimize
the regularity of the fault-tolerant graph. The degree of the fault-tolerant graph is minimized to
reduce the complexity of the system. Also, there are some advantages in requiring the topologies
to be regular. Regular topologies may allow simple routing [14] . Further, VLSI building blocks
such as transputer and iWarp [1] with communication links can be used in designing scalable fault-
tolerant point-to-point networks. Hence, the specifications for the above design problem should
include some optimality criteria. This formulation makes designing fault-tolerant topologies more
challenging. A sketch of the issues in fault-tolerance is outlined in Figure 2.1.

In the remaining part of this Chapter, we present a brief survey of the research in the two
functionality criteria discussed earlier. Studies in both processor and link failures are presented. For
each of the two functionality criteria, the problems presented in this chapter mainly differ by the

optimality criteria and/or design approach taken. Chapter 3 presents the proposed work in detail.

2.1 Preserving a Desired Topology

Designing systems that guarantee a desired topology is referred to as preserving a topology. Sev-
eral researchers have proposed various design methods to preserve a given topology. The basic
design approach to preserve a topology is to employ systemwide redundancy and reconfiguration

[4]. In other words, a fault-tolerant graph is designed by augmenting vertices and/or edges to a

.3:Eo_8-==£ flame—one” .«o baa—.98.“. AN 253m

 

3223:1553_e.ceo_efl_ Eggnog TEE Tezfi .2254— __§§_

 

E _H €22“
_

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

_ A _ _ _ _ _ _ e a
game case“ 323 eggs. hugged gee 55:3 ES 55233 Emma
gee: Seas sea: egg 5%: SE: SE: SE: SE: . .

/ \ a

 

 

I .4 a
_ 85E 55$ _ 83am 0%”: _ ”22$ 55>—

FL _

mean 353

 

    

 

 

seen? 539

”Eco 225:

@3553.

   

 

 

a

€255 a wage: mama?“ Ease;
_ _

gee €55

 

8388. 52925 ”summon

 

 

 

9

given desired graph. Let us consider the designs that tolerate processor failures. This criterion can

be formally defined as follows [4].

Definition 1 Let G (V, E) represent the topology of a CN and D(V, E) be a desired structure. Then,
G is k-node fault-tolerant (k-NFT) with respect to D, iffor any set F C V(G), with IF I S k, the

graph D is isomorphic to a subgraph of G — F.

Using the above definition, several classes of problems can be formulated by imposing 'certain
optimality criteria on the graph G and/or some restrictions on the faulty set F. Hayes [4] considered
minimizing the number of vertices first and then the number of edges. It is easy to see that G must

contain at least k spares. The problem originally proposed in [4] can be stated as follows.

Problem 1 Given a graph D and a positive integer k, construct an “optimal” graph G, which is

k-NFT with respect to D. The optimality criterion is:
(a) |V(G)| == |V(D)| + k

(b) for any G’ that is k-NFT with respect to D satisfying (a), we have |E(G)| S |E(G')|. C]

Let us compute the extremal part of the above problem, i.e., to find the minimum number of
edges in a graph G which is k-NFT with respect to D. From G, remove any set, say F, of k vertices
adjacent to a vertex v, with dega(v) = 6(G). Since G is k-NFI‘ with respect to D, the resulting
subgraph Should contain the graph D. Hence degg_p(v) 2 6(D), which implies 5(0) 2 6 (D) + k.
This also implies that the degree of each vertex in G is proportional to the number of faults to be
tolerated. In [4], three candidates for the graph D are considered, namely, cycles, trees, and simple
paths. In particular, a construction is given for G when D is an even cycle. In this case,’G is a
(k + 2)-regular graph. A similar construction is also given for the case of D being an odd cycle.

The work of Hayes was followed by [2, 5, 6, 7, 8, 9, 10, 11]. In these papers, the authors have

10

adhered to the same optimality criterion, but imposed additional restrictions on the set F. For
example, in [6] the case of D being a binary tree is considered with the additional restriction that
failures only occur at different levels of the tree.

Since the current technology limits the number of possible connections at each processing node
1, the optimality criterion of Problem 1 may not be viable in certain situations [18, 19]. Fault-
tolerant designs which limit the fault-tolerant graph to be regular are studied in [20]. The size and

complexity of the CN is reduced by introducing additional redundancy. Formally,

Problem 2 Given a desired graph D and positive integers k and r, construct a graph G, such that
(a) G is r-regular,
(b) for any set F C V(G) with [Fl 5 k, D is isomorphic to a subgraph of G — F,
(e) no graph H satisfying (a) and (b) above has fewer vertices than G. C]

This approach is more viable since current technology limits the number of possible connections
to each node [11, 20]. It is clear that this problem may not have any solution for certain choices of D,
k, and r. A case in point, when r = 2 and D is a cycle on n vertices, there is no solution G for any h.
Thus 3 is the smallest value of r for which a solution may exist for the case of D = C“. When D =
0,, and r = 3, it is shown in [20] that any solution G must satisfy |V(G)| 2 |V(D)| + 2k. Also, a
construction is given for a class of graphs for which this lower bound is achieved for k = I, 2, and 3.
Very little is known about fault-tolerant topologies when k > 3, r = 3, and D = 0”. Also, no
solution is proposed so far for other desired graphs such as grids, hypercubes, etc.

Now let us consider the designs that tolerate edge failures and preserve a topology. The edge
failure version was recently introduced by Harary and Hayes [21] . The following definition of a

k-edge fault-tolerant graph is due to [21].

 

'it appears that this constraint will persist for some time to come [18, 19].

1 1
Definition 2 Let G (V, E) represent the topology of an CN and D(V, E) be a desired structure.

Then, G is k-edge fault-tolerant (Ir-EFT) with respect to D. if for any set F C E (G), with IF I S k,

the graph D is isomorphic to a subgraph of G — F.

In [21], k-EFT graphs with minimum number of edges were studied. This problem can be

formally stated as follows.

Problem 3 Given a p-order graph D and a positive integer k, construct an “optimal ” p-order

graph, G, such that
(a) G is k-EFT with respect to D,

(b) for any p-order graph G’ satisfying (a), we have E (G ) S E (G’ ) CI

Note that in Problem 3, both D and G are p-order graphs. In other words, in this approach a
fault-tolerant graph is constructed using only spare links. It is easy to verify that 6 (G) 2 5 (D) + k
in any approach that uses only spare links. Further, for certain large values of k the resulting fault-
tolerant graph G is a multigraph. A construction is given in [21] for a class of optimal k-EFI‘
graphs when the desired graphs are simple paths and cycles. In particular, when either I: or n is
even a (k + 2)-regular graph is constructed for D = C”. Also, when the desired topology is an
n-dimensional hypercube, an optimal solution to tolerate one edge failure is given in [21]. We can

also restrict fault-tolerant graph to be regular by using spare processors. Formally,

Problem 4 Given a desired graph D and positive integers k and r, construct a graph G, such that
(a) G is r-regular,
(b) for any set F’ C E(G) with IF’I S k, D is isomorphic to a subgraph of G —— F’,

(b) no graph H satisfying ( a) and ( b) above has fewer vertices than G. ‘ Cl

12

The above design methods which primarily aim to preserve a desired topology have some draw-
backs. We will refer to two of them here. First, these topologies are expensive in terms of the
number of redundant processors/links. For example, when minimum number of redundant pro-
cessors are used, the best known approach to tolerate two processor failures and preserve a 4 x 4
mesh requires 235% more redundant links [2]. Second, there are no tight bounds on the size of the
graph that could preserve topologies such as hypercubes and 2D meshes [2]. On the other hand, the
existing approaches for preserving topological properties are relatively less expensive. However,

preserving a property is not a complete solution to the topological fault-tolerance problem.

2.2 Preserving a Property

This functionality criterion is useful in designing systems that allow graceful degradation. Re-
searchers have taken two approaches in designing property preserving graphs. In one approach, an
optimal property preserving graph is designed, given the order of the fault-tolerant graph. We will
refer to this approach as intrinsic design. This approach is taken because there are some classes
of graphs which are, by definition, property preserving. For example, Km," with m S n, can tol-
erate up to m - 1 processor failures and still preserve the diameter of Kmm. Similarly, a cycle
can tolerate one processor or link failure and guarantee a communication path between each pair
of non-faulty processors. There are several research issues in designing property preserving graphs
with this approach, some of which have been addressed in [22, 23, 24, 25].

Notice that some popular topologies such as path, cycle, k—ary n-cube, may not preserve a given
property after a few failures. In such cases, some redundancies may have to be introduced to make
a given topology preserve a property under failures [26]. This approach is referred to as redundant
design.

As mentioned earlier, topological properties involving connectedness and distance have been

13

studied. Further, in preserving distance, researchers have considered preserving maximum distance

(diameter) of the graph and distance between every pair of non-adjacent vertices.

2.3 Preserving Connectedness

Preserving connectedness considers a CN functional as long as every pair of non-faulty processors
is joined by a non-faulty path. A measure for this property can be given by the connectivity of the
underlying graph. The vertex-connectivity, n(G), of a graph G is defined as the least cardinality
IS I of a set S C V such that G —- S is either disconnected or trivial (i.e., a single-vertex graph). The
edge-connectivity, MG), is defined similarly with S being a set of edges. Using connectivity as
a measure of fault-tolerance implies that if a graph G is the underlying topology of a CN then that
CN can tolerate n(G) — 1 processor failures or A(G) — 1 link failures. Hence designing an Optimal
system that inherently tolerates (k — 1) processor (link) failures and guarantees connectedness can
be designed by an optimal k-vertex (edge) connected graph. Now, we will state the design problems

in preserving connectivity to tolerate vertices/link failures.
Problem 5 Given two positive integers p and k, design a p-order graph G, such that,

(a) rc(G) = k,

(b) for any p-order graph G’ satisfying (a), we have E(G) S E(G'). Ci
Problem 6 Given two positive integers p and k, design a graph p-order graph G such that,

(0) MG) = k.

(b) for any p-order graph G’ satisfling (a), we have E(G) S E(G’). 1]

Let us consider the extremal part of the above problems. A well known result due to Whitney

[27] is n(G) S MG) S 6(G). That is, in any graph the vertex connectivity can at most be equal

14

to edge connectivity, and the edge connectivity can at most be equal to the degree of the graph. It
is clear from Whitney’s result that we must have 6 (G) 2 k. Hence, the minimum number of edges
in a k-connected (k-edge connected) graph is at least [ 55?]. The solutions to the above prOblems
were first given by Harary [22] by constructing a special class of lc-connected (Ir-edge connected)
graphs with [522] edges. This class of graphs are known as Harary graphs. For a survey on this
class of graphs, called circulants, and their connectivities, the reader is referred to [28]. Now, we
will briefly review the problems in designing graphs that preserve connectedness by augmenting

edges to a given graph D.

Problem 7 Given a p-order graph D and a positive integer k, construct a p-order graph G, such

that:
(a) D E G.
(b) G is k-connected,

(c) for any 0’ satisfying (a) and (b) above, we have E(G) 5 E(G’). Cl

Problem 8 Given a p-order graph D and a positive integer k, construct a p-order graph, G, such

that:
(a) D E G.
(b) G is k-edge connected,

(c) for any G’ satisfying (a) and (b) above, we have E(G) S E(G’). [3

Problem 7 is known as k-connectivity augmentation problem. A solution for the 2-connectivity
augmentation problem is presented in [29]. Recently, Watanabe and Nakamura [30] solved the

3-connectivity augmentation problem. When k > 3, this augmentation problem remains open.

15

Problem 8 is known as the k-edge-connectivity augmentation problem. When the given graph
is a tree, the k—edge-connectivity augmentation problem is solved in [31]. Cai and Sun [32] recently
solved the problem when the given graph is a general graph. In [26], it is shown that the weighted
version of this problem is NP-complete.

While preserving the connectivity guarantees the communication between any non-faulty pro-
cessors, the number of intermediate processors involved in message traversal may increase ran-
domly. For instance, let us consider a CN with 0p as its underlying topology. Such a CN can
tolerate one link failure and guarantee a non-faulty path between every pair of processors. Consider
two adjacent vertices u and I). It is easy to see that if the link (u, 1)) fails the distance between ver-
tices u and v is p — 1. To compensate this shortcoming, one can make use of several other measures

in preserving distance.

2.4 Distance

There are two important aspects in preserving distance which have attained the attention of several
researchers. They are the maximum distance in the graph and the distance between every pair of
non-adjacent vertices in the graph. In this section, we briefly review some of the important problems

in these two aspects.

2.4.1 Preserving Diameter

As defined earlier, the diameter of a graph is the maximum distance among all pairs of vertices in
the graph. The delay in transmitting a message in a CN may be measured by the number of inter-
mediate processors between the communicating processors [33]. In this measure, the upper bound
on the maximum transmission delay is a function of the diameter of the underlying topology of the

CN. Hence, to minimize the maximum transmission delay is to minimize the number of interme-

16

diate processors involved between any pair of communicating processors. Research in preserving
a diameter is motivated from designing fault-tolerant CNS in which maximum transmission delay
is critical to keep the system performance. Our interest is in optimal topologies which can tolerate
certain number of failures and still preserve the upper bound on the transmission delays. Intrinsic

design problems to preserve diameter under faults can be stated as follows.
Problem 9 Given positive integers p, k, and d, design a p-order graph G such that

(a) diam(G) = d,

(b) for any F C V(G) with |F| S k, we have diam(G - F) = d,

(c) for any G’ satisfying (a) and (b) above we have E(G) S E(G’). [3
Problem 10 Given positive integers p, k, and (I, design a p-order graph G such that

(a) diam(G) = d,

(b) for any F C E(G) with |F| S k, we have diam(G - F) = d,

(c) for any G’ satisfying (a) and (b) above we have E(G) S E(G’). C]

These problems were first posed by Murty and Vijayan [23], which later received considerable
attention. However, the exact solutions to the above problems have been given only for some special
cases. For example, for Problem 10, the known results are for (d = 2,k _>_ 1, p 2 1), (d g 4, k =
1, p 2 l), and (d = p -— 1,]: 2 1, p 2 1) [25]. Very recently, F.R.K. Chung [25] solved another
special case when (d _>_ 1, k = 1, p 2 1). There are several variations of the above two problems;
However, many problems remain unsolved [25, 34]. A survey of these problems with recent results
can be found in [34].

Similar to Problems 7 and 8, we can construct a diameter preserving graph G by augmenting a

minimum number of edges to a given graph D.

17

Problem 11 Given a p-order graph D with diameter d and a positive integer k, construct a p-order

graph G such that,
(a) D Q G.
(b) for any F C V(G), we have diam(G - F) = d,
(c) any other G’ satisfying (a) and (b) above we have E(G) S E(G’). D

Problem 12 Given a p-order graph D with diameter d and a positive integer k, construct a p-order

graph G such that,
(a) D Q G.
(b) for any F C E(G), we have diam(G — F) = d,
(c) any other G’ satisfying (a) and (b) above we have E(G) S E(G’). , C]

Preserving the diameter is a good criterion to limit the maximum transmission delay. However,
a better design is to be able to keep the transmission delay intact between any communicating
processors. In other words, the interest is in the design of fault-tolerant topologies in which the

distance between the non-faulty processors is not increased after failures.

2.4.2 Preserving Distance

As defined earlier, the distance dG (u, 2)) between two distinct vertices in a graph G is the length of
the shortest path joining the vertices in the graph. Intrinsic designs that preserve distance between
every pair of non-adjacent vertices were first considered by Entringer et a1. [35]. A special class
of graphs in which there are k vertex-disjoint paths of minimum length are studied in [35]. These
graphs are called k-geodetically connected graphs. The following definition of a k-geodetically

connected graph is due to Entringer et al. [35].

18

Definition 3 A graph G is said to be k-geodetically connected if for every pair of non-adjacent

vertices, say u and v, we have at least k vertex-disjoint paths of length d0 (u, o).

In other words, in a k-geodetically connected graph, removal of at least k vertices is necessary to
increase the distance between any pair of non-adjacent vertices. A k-geodetically line connected
graph can be defined similarly. Some properties of k-geodetically vertex (line) connected graphs

are given in [35]. There are two properties that are of interest to us [35].
Property 1 A graph G is k-geodetically line-connected if and only if G is k-geodetically connected.

Property 2 For any pair of vertices u and v in a k-geodetically connected graph G we have

N001) D New) 2 ’6-

By Property 1, it is clear that designing an optimal k-geodetically line connected graph is equal
to designing an optimal k-geodetically connected graph. The problem of designing an optimal

k-geodetically line connected graph can be formally stated as follows.
Problem 13 Given two positive integers p and k, design a p-order graph G, such that
(a) G is k-geodetically line connected,
(b) for any p-order graph G’ that satisfies (a) above, we have E(G) S E(G’). Ci

Exact solution to the above problem is known only for a special case, namely, when diam(G) =
2 and 2k _<_ p; this case was solved by Bollabas and Eldridge [36]. Entringer and Jackson [37]. solved

the case when diam(G) = 2 and 2k > p. The problem remains unsolved for diam(G) > 2.

2.5 Proposed Work

The main subject of this dissertation is the corresponding augmentation problem to tolerate edge

failures and preserve distance when a graph D is given. That is, we construct a distance preserving

19

graph G by augmenting edges to D. Note that by adding an edge to the given graph D, the previous
distance between the end vertices of each new edge is changed [38, 39]. Hence, we propose to
construct a graph in which, between every pair of non-adjacent vertices u and v in D, there are
at least k edge-disjoint paths, each having length at most d D (u, 12). We call the resulting graph as
k-edge distance preserving with respect to D.

The objective of this dissertation is to study the aspects in designing distance preserving graphs.
In Chapter 3, we introduce the problem definition and our design models. In Chapter 3, we Show
that preserving the distance between non-adjacent vertices also sets a bound, in presence of edge
removal, on the distance between vertices which were adjacent before any edge removal. Distance

preserving graphs with respect to some special topologies are presented in Chapter 4.

Chapter 3

Distance Preserving Graphs

3.1 Introduction

Definition 4 Given a connected graph D and a non-negative integer k, a graph G is said to be

k-edge distance preserving with respect to the given graph D, if:
I. D is a spanning subgraph of G and,

2. every pair of non-adjacent vertices u and v in D are joined in G by at least k edge-disjoint

paths, each having length at most dD (u, 22).

Let fk(D) denote the set of all graphs that are k-cdge distance preserving with respect to a

given graph D. Figure 3.1 shows two graphs D and G; where G E f3(D).

 

 

 

 

 

 

 

 

 

 

Figure 3.1: G E .73(D).

20

21

The results provided in the remaining part of this section can be used to check the validity of

the constructions presented in this dissertation.

3.2 Preliminaries

Property 3 For any graph D on p vertices we have .7: _1(D) = {KP}.

Property 4 For any graph D on p vertices we have fk+1(D) Q fk(D)for any k, 1 S k < p — 1.
Property 5 For any graph D on p vertices the set fk(D) is not empty for any k, 1 S k < p.

Lemma 1 Let G be a k-edge distance preserving graph with respect to a given graph D. Then for

every pair ofvertices u and v with dD(u, v) = 2, we have lNa(u) fl Nc(v)| _>_ k — 1.

Proof: By the definition of a k-edge distance preserving graph, we know that G contains k
edge-disjoint u-v paths of length at most 2. Since G is a simple graph, there can be at most one
edge connecting the vertices u and 12. There remain at least k -— 1 paths and each path must have
only one intermediate vertex. Hence lNg(u) n Na(v)| 2 k — 1. Note that if it turns out that the
edge (u, 1)) ¢ E(G), then we have |Ng(u) n Ng(v)| 2 k, since in this case all the k edge-disjoint

u-v paths in G are of length two. 1 Ci

Corollary 1 Every graph G in .‘Fk (D) is at least k-connected. Ci

3.3 Characterization Result

Theorem 1 Let D be a p-order graph and k < p be a non-negative integer: F urthet; let G be

a graph having D as a spanning subgraph, and if u and v are non-adjacent vertices of D such

22

that d D (u, v) S 3, then there are k edge-disjoint paths between it and v in G, each having length

dD(u,v) or less. Then G E PAD).

Proof: We will consider an arbitrary pair of vertices u and v in D and inductively construct a set
of k edge-disjoint u-v paths in G of length at most dD(u, v). The following notation is useful. For
any two vertices a: and y in a path P, we denote by PM”, the portion of P connecting the vertices
x and y.

Basis : If dp(u, v) S 3, then by the way G is defined there are k edge-disjoint u-v paths in G
of length at most dD (u, v).
Hypothesis : For every pair of non-adjacent vertices u and v in D, with dp(u, v) < n and In 2 4,
there are k edge-disjoint u-v paths in G of length at most dp(u, 1)).
Induction Step : Consider a pair of non-adjacent vertices u and v in D such that dD(u, v) = n;
if no such pairs exist, we are done. Consider the vertex w on a shortest u-v path in D such that
dD(u, w) = n — 2. By the induction hypothesis, there are k edge-disjoint u-w paths in G of length
at most dD(u, to). Let P = {P1, P2, . .. , Pk} be such a set of k edge-disjoint paths. From the way
we chose w, the vertices w and v are distance two apart in D and hence there are k edge-disjoint w-v
paths in G of length at most 2. Let Q = {(21, Q2, . .. , Qk} be such a set of k edge disjoint paths.
Also by Lemma 1 we know that at least k — 1 of the paths in Q are of length two. “Without loss of
generality, let Q,- = w, q,-,v, 1 S i < It. Further let qk = to if Q), = 10,12; otherwise, Q), = w, qk,v.
Using the paths in P and Q we construct, ’R, a set of k edge-disjoint u-v paths in G of length at
most dD(u, v).

We call a path P in P as used if P is used to construct a u-v path in ’R. Initialy all the paths in
P are unused. Also, we mark a vertex q,-, 1 g i g k, as visited if the edge (Qt, v) E E(G) is used
in constructing a we path in R. Initialy, all vertices q,-, 1 S i S k, are marked unvisited.

Step 1: For each path P E P,

23

 

Figure 3.2: Example: k = 3, dD(w, v) = 2 and dG(u, w) 2 3.
Case: 1) E V(P)
If v is an intermediate vertex in P then Pu.W e R; mark P as used. The path Pu.W is of
length at most dp(u, 1)), because P is of length at most dD(u, w) < do (u, 2)). Note that any

such path Pu...” can have at most one edge (qj, v), 1 S j S k. If such a vertex qj exists, mark

q,- as visited.

Case: v a! V(P)

In this case, the path P may contain zero or more unvisited vertices (It. 1 S i S k.

Subcase: P contains one or more unvisited vertices
Let qj be the first unvisited vertex encountered when traversing the path P from u to w.
Then we construct a new u-v path in R by augmenting the path Pu...” with edge (q,-, u),
and then mark the vertex q,- as visited. It is easy to see that such a u-v path is of length
at most dD(u, It). Further, the constructed u-v path is mutually edge-disjoint with all
the existing paths in R as all paths in P are edge-disjoint and the vertex q,- is not visited
before.

Subcase: P contains no unvisited vertex

In this case the path will remain unused and will be processed in Step 2.

Note that, each time we construct a path in R we mark at most one more vertex qj, 1 S . j S k,

as visited. Hence, after the above construction, the number of unvisited vertices in G is at least as

I:
P
<
H—O
rig

 

Figure 3.3: Graphs G and H are not in f3(D).

many as the number of unused paths in P. If a vertex q,-, 1 S j S k, is still unvisited, it implies that

both the edges (w, q,-) and (qj, u) do not exist in any unused path in P.

Step 2: For each unused path in P E P
Construct a new u-v path by appending the path w, q,-, a to P, where q,- is some unvisited vertex.
It is easy to see that each such we path in G is mutually edge-disjoint with the paths in R and of
length at most dp(u, w) + 2 S dD(u, 2)). Hence, by using each of the k paths in P we construct a

set of k edge-disjoint u-v paths in G of length at most dD(u, v). D

An example explaining the above construction is given in Figure 3.2. Figure 3.2 represents a por-
tion ofa graph G e f3(D), for some D. Let P = {P1, P2, P3}, where P1 = {u, . .. , q], u, qz, w},
P2 = {u, . .. , ql, w} and P3 = {u, . .. ,q3, w}. The above construction first considers P1. Since
I) 6 P1, R1 = Plu~v and vertex q] is marked visited. The path P2 does not contain any unuisted
vertex. Hence, path P2 will still be marked unused and path P3 is considered next. Since P3 con-
tains one unvisited vertex, q3, the new path R3 is {P3qu3 ,v}. The vertex Q3 is marked visited. Now
in step 2 the remaining unused path, P2 is considered. A new we path is constructed by augmenting
P2 with path w, (12, v.

The above theorem implies that to prove a graph G belongs to fk(D), it is enough to show that
every pair of vertices u and v with dp(u, v) S 3 are joined in G by k edge-disjoint paths of length

at most dp(u, 12). Figure 3.3 shows an example in which every pair of vertices having distance two

25

in D are joined by 3 edge-disjoint paths of length at most two in G. However, for the vertices u and
w, with dp(u, w) = 3, there are only 2 edge-disjoint paths of length at most three in G. Similarly,
all the vertices which are distance three apart in D are joined by 3 edge-disjoint paths of length at
most three in H; but the vertices u and v with dD(u, v) = 2, are not joined by 3 edge-disjoint paths
of length at most two in H. Hence, the above two examples show that the sufficiency condition
given in Theorem 1 is sharp.

In this chapter, we present two models in designing distance preserving topologies that tolerate
edge failures. In the first model, the optimality criterion is to minimize the number of edges. The
second model considers regular fault-tolerant topologies with minimum regularity. In Sections 3.4
and 3.5, we present our models and lower and upper bounds when the given graph is a general
graph. We also prove that the given bounds are tight. In Chapter 4, we present constructions for

cycles, crowns, chordal rings and n-ary 2-cubes.

3.4 Model 1

Model 1 Given a graph D and a positive integer k, construct a graph, G, such that:
(a) G 6 MD).

(b) for any G’ E f'k(D), we have |E(G)| S |E(G’)|. Ci

3.4.1 Bounds

Since we consider only simple and connected graphs, it is assumed in the rest of the dissertation
that k < |V(D)|. For any graph D on p vertices, if G belongs to fk(D) then it is easy to see that
6(G) Z k. Hence, for any G E fk(D), we have |E(G)| 2 [1°23]. Note that the example graph G in

Figure 3.1 belongs to f3(D); however, it is not of minimum size. The graph Gopt in Figure 3.4 is a

26

 

 

 

 

 

 

 

 

 

 

opt
Figure 3.4: Gopt E f3(D).
minimum Size graph. The graph Gopt in Figure 3.4 uses [if] edges.
The following lemma gives an upper bound on the size of the augmentation. Before we present

the upper bound on the size of the augmentation let us define a graph H 2‘ K], + 71,4.

Lemma 2 Given any p-order graph D and a non-negative integer k < 19, there exists a graph

G 6 mp) such that |E(G)| — |E(D)| g (’2‘) + k(p — k) — |E(H) n E(D)|.

Proof: We will construct a new graph G from D by adding at most (5;) + k(p — k) edges.
Since D is a spanning subgraph of G, we Start with V(G) = V(D) and E(G) = E(D).
Label the vertices of G as 121,122,... ,vp such that degD(v,-) 2 degp(v,-+1), 1 S i < p. Let
Vk = {v1,v2,... ,vk} Q V(G). If(v,-,vJ-) ¢ E(G),for1 S i S kandl S j 5'5 i Sp,thenaddthe
edge (22,-, vi) to E(G). Hence, the total number edges added is S (2L1 — i)) — |E(H) n E(D)|
= 5&2:th —— |E(H) n E(D)| = (’2‘) + k(p — k) — |E(H) n E(D)|. It is easy to see that such a
graph G belongs to fk(D). Note that if k = p — 1, the above construction results in a chplete

graph. D

Figure 3.5 shows a complete binary tree of height two. Figure 3.6 shows a construction for
k = 2 and when the graph D is a complete binary tree of height two; the set V), is Shown in’Figure
3.6. Now we will show that the given upper bound is tight for certain values of I: when the given

graph, D, is a star graph.

27

4 5 6 7

Figure 3.5: A complete binary tree of height 2.

 

Figure 3.6: K2 + H5 6 .7), (complete binary tree of height 2).

Definition 5 A p-order star graph, say S , can be defined a graph with vertex set {120,111, . . . ,vp_1}
and for each vertex 1),, 1 S i < p, we have (v0, 11,-) E E(Sp). Vertex v0 is referred as the source

vertex.

A 9-order star graph is shown in Figure 3.7.

Theorem 2 Given two non-negative integers p, k where k < E, and a graph D = Sp, the minimum

Source vertex

1P
D

 

0

Figure 3.7: A 9-order star graph.

28

 

 

 

 

 

Figure 3.8: Case 6(H) = k.

number of edges in a graph G E TAD) is at least figLE’ET—IL

Proof: Let V(D) = {120,121, . .. ,vp_1}, where v0 is the source of Sp. Let us assume that there
exist a graph H E fk(D) with |E(H)| < EEK-#1.

Consider a vertex in H, say v1, such that degg(v1) = 6(H). Let X = N(v1) and Y =
V(H) — X — {121}. Note that v1 is connected to every vertex in X. And vertex co, the source
of the star graph, is connected every vertex in {X} + {121} — {120}. First let us consider the case
when 6(H) = k (Figure 3.8). Since there are k edge-disjoint paths from It; to each vertex in
V(H) - {120,221}, each vertex in X -— {be} is connected top - 3 vertices in V(H) — {vo,v1}. In
other words, the degree of each of the k vertices in X is p — 1. Hence the total number edges in H
is W < HZL-zk—‘u—a contradiction.

Now consider the case when 6 (H) = k + i, for some non-negative integer i > 0; Figure 3.9

shows such a graph H. The total number of edges in H is the sum of,

(k + i): Number of edges from 121.

29

ME): Number of edges between vertices in X. Since there are
k edge-disjoint paths from 111 to each vertex in X — {120},
each vertex in X is connected to at least (k — 1) other
vertices in X.

(p — k — i — 1)k: Number of edges between vertices in X to the vertices in Y.
Since there are k edge-disjoint paths from 121 to each
vertex in Y, each ofthe (p — k — i — 1) vertices in Y
is connected to at least k vertices in X.

m: Thedegreeofeachofthe(p—k-i—l)

vertices in Y is at least k + i.
Which implies,

(k + i) + MLék—‘dl + (p _ k _ i __ l)k + (E-kgi—lzi < “22-51;-”

2k+2i+k2-k+ki—i+2kp—2k2-2ki—2k+JIi—ki-i2—i < 2kp—k—k2
2

=> 2

=> pi—2ki—i2<0

=> p-k<k+i

Hence,
p-k+1sa(H) (3.1)

Hence the number of edges in H is at least

(P-llflP-IXP-H'D < k(2P-k-1)
2 2

: (2-1)(E—k+2)<k(2p-k—I)

2 2

30

=> p2+p(1—3k)+k2+2k—2<0

 

___> p < (3k—l)ifll-3;)3—4(k2+2k—2)

< (3k—1):l:\/5k5—14k+9
2

 

 

=>P

 

, (3k—1)+\/5k’—14k+9
Case . p < 2

Sincek>0,p<Q’-°;1-§t—- 'g’cz

=>P< 6k2—1

A contradiction.

(3k—1)—\/—5k7——14k+9'
2

 

Case: p<
Sincek>0,p<fi’°2;l-l

A contradiction.

Corollary 2 Given a graph D = S , and a non-negative integer k S g the minimum size of an

augmentation to construct a graph G E fk(D) is £22ng — (p — 1). C]

From Corollary 2, it is easy to see that the bound given in Lemma 2 is tight.

The optimality criterion used in Model 1 is to add a minimum number of edges. But, regular
topologies are desired in designing modular systems [20]. Hence, we shift our optimality criterion
from minimum number of edges to minimum regularity. In the rest of the dissertation, we study

designing optimal graphs in this model.

3.5 Model 2

31

 

 

Y «o- .
1 i : "'E-._:.vk+i+l é
. \z-J : ~13. mi: :
Required edges 33in; 1'33 5
""""""" Possible edges 1 ":- :.;5'2I."' 5
' "'1' '1 I
5"; : : E
: t. : i :
”—3” a... :
(p-k-i-l)kcdges .--__---.f' "Ev '

Figure 3.9: Case 6(H) = k + i.

Model 2 Given a graph D and a positive integer k, construct a graph G such that:

(a) G E fk(D).

(b) G is r-regular; and

(c) for any r’ -regular graph G’ E fk(D), we have r S r’. [3

3.5.1 Bounds

Let p = |V(D)|. Since Kp E .75).,(D), it is obvious that the upper bound for r is p — 1. For the lower
bound, since a graph G E .Pk(D) is at least k-edge connected, we have r 2 k. In the remaining
part of this section, we prove that for certain values of k, there are no k-regular graphs in IND), in
which case the lower bound for r is (k + 1). But before proving this statement, we give some useful

properties of k-regular graphs in f'k(D).

32

 

1A 1‘ 1‘ 1‘

Figure 3.10: Case 1: (u,x) E E(G) : (u, v) 6 E(G).

N(u) = N(v)
r/

 

 

 

Figure 3.11: Case 2: Ng(u) = Ng(:c) => Na(u) = Na(‘i}).

33

Property 6 For a given graph D, if there exists a k-regular graph G E fk(D) then for every pair

of non-adjacent vertices u and v in D, we have either (u, v) E E(G) or Ng(u) = N0(’U).

Proof: Let us consider an arbitrary pair of non-adjacent vertices u and v in D. We will prove the
above property by induction on d D (u, v).

Basis : If dp(u, v) = 2 then the validity of the property can be deduced from the proof of Lemma
1. If dD(u, v) = 3, we will Show that the edge (u, v) must belong to E(G). Consider the vertex w
on a shortest u-v path in D such that dD(u, w) = 2. Since the graph G is k-regular, the edge (w, v)
must be used in one of the k edge—disjoint u-w paths. Further, since any such u-w path is of length
at most two, the edge (u, v) must belong to E(G). This implies (u, v) E E(G). This completes the
verification of the basis.

Hypothesis : For every pair of non-adjacent vertices u and v in D with 2 S dD(u, v) < n, either
(u,v) E E(G) or Ng(u) = Ng(v).

Induction Step : Consider a pair of vertices u and v in D such that dp (u, v) = n, and not
satisfying the hypothesis; if no such pairs exist, we are done. Let :c be the vertex on a shortest u-v
path in D such that dD(u, :c) = n — 2. By induction hypothesis, we know that either (u, :r) E E(G)
or Nc;(u) = Ng(.v). Note that from the way we choose 2:, the vertices a: and v are distance two
apart in D. Therefore, we have k edge-disjoint m-v paths in G of length at most two. Now, we have
two cases to consider.

Case 1 (u, x) 6 E(G): Since G is k-regular, one of the k edge-disjoint z-v paths must use the edge
(u, 2:). Further, any such path can be of length at most two (Figure 3.10). Hence the edge (u, v)
must belong to E(G). This implies (u, v) E E(G).

Case 2 Na(u) = Ng(:c): Let such a set be {y1,y2, . .. ,yk} (Figure 3.11). Since G is k-regular,
each of the k edge-disjoint x-v paths in G must start with an edge (2:, y,-), where 1 S i S k. Since

any such path can be of length at most two, the edge (y,-, v) must be in E(G) for all i, 1 S i S k.

34

This implies {y1,y2,... ,yk} Q Ng(v). Since degG(v) = k, we have Ng(v) = {y1,y2, . .. ,yk}.

Hence Nc(u) = NG(v) = {y1, y2, . .. , yk}. This concludes the proof of the property. [3

Corollary 3 1 Given a graph G and vertex set {u, 2:, v} Q V(G), if there exists a set of k edge-
disjoint u-a: paths in G of length at most (1 and a set of k edge-disjoint .v-v paths in G of length at

most 2, then there are k edge-disjoint u-v paths in G, each having length d + 2 or less. [I]

Property 7 Given a graph D, if there exists a k-regular graph G E fk(D) then the diameter of G

is at most 2.

Proof: The proof of this property immediately follows from Property 6. ' El

Theorem 3 Given a graph D, if there exists a k-regular graph G 6 fk(D) then the order of the

graph D (and G) is at most 2k.

Proof: Letp = |V(D)| = |V(G)| and V,- be the set of all vertices that are distance i > 0 away from
u inG. By Property 7, we havei S 2. Sincethe graph Gis k-regular |Vl| = kand |V2| =p—k— 1.
By Property 6, for every vertex v 6 V]; we have Na(u) = Ng(v); i.e., every vertex in V2 must
be connected to all the k vertices in V1. But each vertex in V1 can be connected to at most k — 1

vertices in V2, hence p — k — 1 S k — 1. This implies p S 2k. C]

Corollary 4 For any p-order graph D and any non-negative integer k < 2, there does not'exist a

k-regular graph G E .Pk(D). D

 

lThis corollary follows immediately from the “Induction Step ” of proof for Theorem I.

 

 

 

Figure 3.12: K5,5 E f5(K5,5) and diameter of K55 is 2.

It is clear from Corollary 4 that for any k < If, the degree of regularity of a graph in .Fk(D) is at
least (k + 1). Before we present our designs for some special topologies, we address the issue of

the distance between adjacent vertices upon edge removal.

3.6 A Bound on the Diameter of G

It is interesting to note that there exist graphs D and G such that G E fk(D) and after removing a
set of F edges, |F| < k, in G we have diam(G —F) > diam(D). For instance, consider a complete
bipartite graph Km", for any n > 1; diam(Knm) = 2. In Km", every pair of non-adjacent vertices
are joined by n edge-disjoint paths of length 2. Therefore, we can remove up to n — 1 edges and
still preserve distance between non-adjacent vertices in Km“. In other words, Kn,“ E fn(Kn,n).
Since n > 1, remove any edge, say (u, v), then we have diam(Kmn — {(u, v)}) > 2. Figure 3.12
shows a complete bipartite graph of order 10. Figure 3.13 shows a K 55 — {(0, 1)} in which vertices
0 and 1 are distance 3 apart. Hence preserving distance may not necessarily preserve the diameter.
In the remaining part of this section, we present an upper bound on diam(G — F). First we present

a property which is crucial in providing an upper bound for diam(G — F).

36

 
    

r
it

t
t
s

/
"
w,
\W

.3:
t/

 
     

{A
\V; 4
Q
(A v 4
9’
\

   

 

Figure 3.13: Diameter of [(5.5 - {0,1} is 3.

Property 8 Given a graph D and a graph G 6 fk(D) with k < |V(D)|. For any F Q E(G)
with |F| < k, if diam(G — F) > diam(D) then for every pair of vertices u and v in G with

dG~p(u,v) = diam(G — F), we have (u, v) E E(D).

Proof: Suppose otherwise and let (u, v) ¢ E(D). This implies u and v are non-adjacent vertices
in D. Since G e fk(D), by definition, there are k edge-disjoint u-v paths in G of length at most

dD(u, v). Implying diam(G — F) = dc- p(u, v) S dp(u, v) S diam(D)—a contradiction. Cl

Corollary 5 Given a graph D and a graph G E 37-],(D) and a set of edges E with |F| < k, If

diam(G — F) > diam(D) then diam(G — F) is bounded by max{da_p(u, v)|(u, v) E E(D)}.D

For any pair of adjacent vertices u and v in D, the following theorem presents an upper bound
on the distance between it and v in G — F. To follow the proof of the theorem a brief defi-
nition of eccentricity is necessary. Given a connected graph D and a vertex u E V(D), the

eccentricityp(u) = max{dp(u,v)|v E V(D)}.

Theorem 4 Given a graph D and a graph G E .7); (D) with k < |V(D)|, for any pair of adjacent

vertices u and v in D andfor any F Q E(G) with |F| < k, we have dg_p(u, v) S 5.

37

Proof: The proof is given by constructing a set of k edge-disjoint u-v paths in G of length at most 5.
“Without loss of generality, assume that eccentricityp(u) 2 eccentricityp(v). First consider the
case when eccentricityp(u) 2 3. Let :1: be a vertex such that dD(u, z) = 3. Let P = u, l, m, :1: be
a we path of length 3 in D. Since (u, v) E E(D). we have dD (v, x) 2 2; otherwise, dD(u, x) < 3.
Similarly, dp(v, 2:) S 4 because v and :r arejoined in G by a path of length 4 namely, v, u, l, m, x.

In other words, we have 2 S dD (v, :c) < 4

Case dD(v,:r) 2: 2: We have dD(u,a:) = 3 and dD(v,:r) = 2 and since G 6 fk(D), by Corollary

3, there are k edge-disjoint u-v paths in G, each having length 5 or less.

Case dD(v,:r) = 3: Let us consider the vertex m in the path P. We know that dD(u,m) = 2.
Notice that dD(v,m) > 1; Otherwise, dD(v,:c) < 3. Also, dD(v,m) S 3 because v,u,l,m
is a v-m path in D. In other words, we have 2 S dD(v,m) S 3. Since G E fk(D) and
d D (u, m) = 2, by Corollary 3 we have k edge-disjoint u-v paths in G, each having length at

most 5.

Case dD(v,:r) = 4: Consider the vertex m in the path P; we have dp(u, m) = 2. Since we have
a v-m path v,u,l,m in D, we have dD(v,m) S 3. But note that if dD(v,m) < 3, then
dD(v,:r:) < 4, a contradiction. Hence dD(v, m) = 3. By Corollary 3, we have at least k

edge-disjoint u-v paths in G, each having length at most 5.

Now let us consider the case when eccentricityp(u) S 2 and eccentricityp (v) S 2. If
eccentricityp(u) = 1 or eccentricityp(v) = 1, then all the vertices in D are adjacent to either u
or v. However, if eccentricityp(u) = 2 and eccentricityp(v) = 1, since 6(G) 2 k, it is easy to
see that ING [u] O Na[v]l 2 k. This implies that there k edge-disjoint u-v paths of length at most 2.
Hence, without loss of generality, we assume that eccentricityp(u) = 2 and eccentricityp(v) =

2. If there exist a vertex w which is distance 2 away from both it and v in D then, by Corollary 3,

38

we have k edgedisjoint u-v paths in G, each having length at most 4 and we are done. If such a w
does not exist then each vertex in V(D) is either adjacent to u or adjacent to v. In such a case, we
claim that there are k edge-disjoint u-v paths in G of length at most 3. In the remaining part of the

proof, we enumerate a set of k edge-disjoint u-v paths in G, each having length at most 3.

Since (u, v) E E(G), there is one u-v path of length 1 in G. Let L = Ng(u) n Ng(v) and
let I = |L| _>_ 0. By using the vertices in L, we can construct a set of l edge-disjoint u-v paths of
length 2. So far, we have l + 1 number of edge-disjoint paths of length at most 2. If k S l + 1, we
are done. Otherwise, since 6 (G) 2 k we have at least (k — l — 1) unused vertices adjacent to u.
Similarly, there are at least (k — l — 1) unused vertices adjacent to v. Let us denote by M and N
the set of unused vertices adjacent to u and v, respectively; It is easy to see that M n Na(v) = 0
andNnNG(u) = (0. Sincek > l+1,wehaveM aé 0,N 74 0. NoticethateachvertexinMis
distance 2 away from v in D, implying that there are at least k edge-disjoint paths in G of length
at most 2 from each vertex in M to v. Consider any vertex u,- 6 M. Since M n Ng(v) = 0, by
lemma 1, we must have Ng(u,-) n Ng(v) 2 k. However, u,- can at most be connected to l + 1
vertices of L U {u}. The remaining (k — l - 1) vertices in Na(u,) n Na(v) must belong to N. In
other words, for each u, E M we have |Ng(u,-) n N| _>_ (k — l — 1). Since |M| _>_ (k —‘l — 1)
there exist a matching of size at least (k — l - 1) from vertices in M to the vertices in N. Since
all vertices in M are connected to u and all vertices in N are connected to v, there are (k - l -- 1)
internally disjoint u-v paths, each having length 3 in G. To summarize this case, there is one u-v

path of length 1, l u-v paths of length 2 and (k — l -— 1) u-v paths of length 3 in G. [3

Corollary 6 Given a graph D and a graph G 6 fk(D), with k < |V(D)|. For any F Q E(G)

with |F| < k, we have diam(G — F) S maa:{5,diam(D)}. D

39

In this chapter, we formulated two design models and their tight lower and upper bounds. In the
next chapter we consider certain special topologies as D and construct distance preserving graphs

for Model 2.

Chapter 4

Special Topologies

In this chapter, we design fault-tolerant topologies for cycles, crowns, chordal rings and n-ary 2-
cubes. These graphs are highly symmetric and attractive for communication networks due to their
regularity, symmetry, and small diameter. The connectivity and reliability of this class of graphs

have been studied extensively by many researchers [2, 28, 42, 43, 44, 45].

Definition 6 A cycle of order p, referred as C , can be defined as a graph with vertex set

{vo,v1, . .. ,vp_1} andfor each vertex vi, 0 S i < p, we have (vi, v(,+1) mod p) E E(Gp).
A 015 is shown in Figure 4.1.

Definition 7 ’ A r-regular crown, called r-crown, of order p is a bipartite graph with partitions V0
= {v0,v2, . .. ,vp_2} and V1 = {v1,v3, . .. ,vp_1},' each v,- in V}; is connected to v(,-+2j_1) mod p,

0 S j < r.
A 5-crown of order 16 is shown in Figure 4.2.

Definition 8 A chordal ring C(p, h), where p is even and h S g is odd, can be defined as a

3-regular graph with vertex set {vo,v1, . .. ,vp_1}, and for each even vertex v,- in V(G(p,h)),

 

lSince |V1| = g, p 2 2r.

41

15 1
14 2
l3 3
12 4
11 5
10 6
9 7
8
Figure 4.1: Gm.

 

Figure 4.2: A 5-regular crown of order 16.

 

Figure 4.3: A C(16, 7).

(”ova“) mod p) E E(Cm h» and (viiv(i+h) mod p) E E(C(P,h))-

A generalized chordal ring G (p, < h1,h2, . . . ,h, >) can similarly be defined with multiple
odd chords hl < h2 < < h, S 35-. Figures 4.3 and 4.4 show a C(16, 7) and C(16, < 5,7 >).

respectively.

Definition 9 A n-ary 2-cube can be defined as a graph, say G, of order n x n with vertex set
{v(,-’j)|0 S i,j < n}. Andfor each vertex v(,-’j) we have (v(,-,j),v(((,-+1) mod fly”) 6 E(G) and

(”servers“) mod n» E E(G)-

A 8-ary 2-cube is shown in Figure 4.5.

4.1 Cycles

In this section, we show that a class of (k + 1)-regular graphs is k-edge distance-preserving with
respect to 0,, a cycle of order p. For even values of k, the regularity of the distance-preserving
graphs is odd. For a regular graph, both the degree and order cannot be odd. Hence to give a general

construction, we assume that the order of the graph is even.

 

Figure 4.4: A C(16, < 5,7 >).

 

Figure 4.5: A 8-ary 2-cube.

lstFCfromO

 

lst BC from 1
2nd BC from 3

 

2nd FC from 0

 

 

Figure 4.6: A 3-crown on 12 vertices.

Theorem 5 A p-order (k + 1)-crown belongs to fk(Gp).

Proof: Since crowns are Hamiltonian [28], G1, is a spanning subgraph of a p-order (k + 1)-crown.
Due to Theorem 1, it suffices to show that each pairs of vertices that are distance two apart in 0,,
are joined by k edge-disjoint paths of length at most two, and vertices that are distance three apart
in 0,, are joined by k edge-disjoint paths of length at most three. Note that in a G , only vertices of
form v.- and v,-+2 are distance two apart, and vertices of form v,- and v.43 are distance three apart.

The following notation will be useful in the remaining part of the proof. If {v0, v1, . .. ,vp_1}
is the vertex set of a graph then the vertex v,- is referred to as an even vertex if i is even and odd
otherwise. In a k-crown, if v,- is an even vertex, we call the edge (v,,v,-+2j_1), 0 S j < k, as
the 3"“ forward chord (PC) from vertex v, and the 3'": backward chord (BC) from vertex «hm--1.
Specifically, if v; is an odd vertex, the edge (v1, v¢_.2j+1) is the j‘h BC from v). Each even vertex in
a k-crown has k FCs, and each odd vertex has k BCs.

An example of a 3-regular crown on 12 vertices is shown in Figure 4.6. The edge (0,1) in'Figure
4.6 is called the first PC from vertex 0 and the same edge is called as the first BC from vertex 1.

First let us consider a pair of vertices, say v,- and v.-+2, that are distance two apart in 0?. Since
crowns are known to be point-symmetric graphs [42], without loss of generality, we assume that v,-

is an even vertex. To prove that there are k edge-disjoint paths of length two between v,- and v,-+2,

45
1+1

i i+2

i+2k-l

Figure 4.7: A set of k edge-disjoint paths between v,- and v,-+2 of length 2 in a (k + 1)-crown.

i+5 k-th BC i+6-2k

 

k-th BC

 

k-th BC

 

 

 

 

Figure 4.8: A set of k — 3 edge-disjoint paths of length 3 in a (k + 1)-crown.

it suffices to show that IN (v,-) n N (v,+2)| = k. By definition, in a (k + 1)-crown we have N (v,) =
{vt+2j—1 E V(G) I 0 S j S II7}- Similarly, N(‘Ui+2) '-' {vt+2j+1 E V(G) l 0 S j S k}- It is easy
to see that |N(v,-) fl N(v,+2)| = k.

A set of k edge-disjoint paths of length 2 between v,- and v,-+2 is shown in Figure 4.7.

Let us consider a pair of vertices, v,- and v,-+3, that are distance three apart in 0,. First we will
construct a set of three paths between vertices v,- and v,-+3 of length at most three. These paths are,
P1: {v,,v,-+1,v,-+2,v,-+3 }, P2: {v,,v,+3 }, and P3: {v,,v,-+2k-1,v,-+4,v,-+3 }. It is obvious that

the above three paths between v,- and v,-+3 are pair wise edge (vertex) disjoint. The next (k — 3)

46
paths are as follows. For each j, 3 S j S k — 1, we have, PJ- = {v,~, v,-+2j_1, v,-+2j_2k,v,-+3}. Now
we will show that the above (k - 3) paths are edge (vertex) disjoint.

Let At = {vt+5,vt+7,--- ,vt+2j—1,-~ avi+2k-3} = {vt+2j—1 E V(G) I 3 S j S k - 1} E
N (v,-). Note that all the vertices in A,- are odd, distinct, and unused. Similarly, let 11,-4.3 =
{vi-2an—4a-u avi+2j—2ka--- avi+6-—2k} = {vt+2j—2rc E V(G) I 3 S j S k - 1} Q N(vi+3)-
Note that all the vertices in A,+3 are even, distinct, and unused.

Now take the kth BC from each vertex in A5. The set of vertices reached by using the
k“h BC from each vertex in A,- can be given as {v(,-+2j_1) _(2k_1) I 3 S j S k 4 1} =
{”(i+21'-2k) I 3 S j S k - 1} = 11,43. Hence from the (k — 3)-vertices in A,- we can reach the
(k—3) vertices in Ai+3, using k—3 distinct edges. In a (k+l)-crown we have N (v,)r)N (v,-+3) = (b.
This implies that the constructed set of (k — 3) paths between v,- and v,-+3 are pair wise edge (in
fact, vertex) disjoint. The set of (k — 3) edge-disjoint paths between v,- and v,-+3 is shown in Figure

4.8. This concludes the proof of the theorem. 1:]

Using Corollary 4, it is easy to see that the above construction is optimal. Figure 4.9 shows a

set of 4 edge-disjoint paths of length at most 3 between v0 and v3 in a 5-regular 16-order crown.
Theorem 6 A complete bipartite graph on p vertices, Kg; 6 f; (GP).

Proof: It is easy to see that a 0,, is spanning subgraph of a complete bipartite graph. Due to
Theorem 1, it suffices to show (1) that the vertices that are distance two apart in C'p are joined by
k edgedisjoint paths of length at most two, and (2) vertices that are distance three apart in C? are
joined by k edge-disjoint paths of length at most three. Note that in a C , only vertices of form v,-
and v,-+2 are distance two apart, and vertices of form v,- and v.43 are distance three apart. Also, the
vertices that are distance 2 apart in G, belong to the same partition of the bipartite graph. Hence,

it is easy to see that any such vertex pair has exactly 5 vertices common to both vertices. Now let

 

Figure 4.9: A set of 4 edge-disjoint paths between on and v3.

us consider the vertices that are distance 3 away. Note that in a Up the vertex pairs that are distance
3 apart are of the form v,- and v,-+3. Since the bipartite graphs are point symmetric, without loss of

generality, assume that such a pair is v0 and v3. The k edge-disjoint paths can be given as,

lst path: vo,v1,v2,v3.
2nd path : v0, v3.

3rd — k‘hpaths : vo,v2,-+1,v2,-,v3, where 2 S i < k - l.

The proof of Theorem 5 can be used to show that the given k edge—disjoint paths are edge (vertex)

disjoint. D

The above two theorems provide an optimal solution for Model 2 when D = C, and k S g. In
the remaining part of this section, we construct distance preserving graphs for other topologies such

as crowns, chordal rings, and n-ary 2-cubes.

48

4.2 Crowns

Theorem 7 A p-order (r + k — 1)—crown belongs to fur-crown), for any non-negative integer

k(ifl’fll.

2

Proof:2 By definition, a p-order r-crown is a spanning subgraph of a p-order (r + k — 1)—crown.
Due to Theorem 1, it suffices to show that ( 1) each pairs of vertices that are distance two apart
in an r-crown are joined by k edge-disjoint paths of length at most two, and (2) vertices that are
distance three apart in an r-crown are joined by k edge-disjoint paths of length at most three. Since
crowns are known to be point-symmetric graphs [42], without loss of generality, we assume that
our “source” vertex is v0. First, we will consider vertices that are distance two apart in an r-crown.
Note that in an r-crown all the pairs of vertices that are distance two apart are of the form’vo and
v2], 1 S l < r. Figure 4.10 shows a 5-crown and vertices that distance 2 away from v0. It is easy
to see that in an (r + k — 1)-crown, the k edge—disjoint paths joining v0 to v21, 1 S l < r, are
vo,v2j_1,v2], where r — 1 S j S r + k — 2.

Now, we will consider all the vertices in an r-crown that are distance 3 away from v0. In an
r-crown, it is easy to verify that vertices v2,._2 and vp_2,+2 span all the vertices that are distance
3 away from v0. In other words, a shortest path to all the distance 3 away vertices from v0 can be

given by,
(a) vo, vzr—s, v2r—2, v2r+2z_3. for some I. 1 S l < r. and
(b) vo,vp_1,vp_2,+2, vp_2,+2;_1, for some I, 1 S l < r.

Therefore, if a vertex v,- is distance 3 away from v0, we have either 2r — 1 S j S 4r — 5 or,

p — 2r + 1 S j S p — 3. Figure 4.10 shows a 5-crown and vertices that distance 3 away from v0.

 

2Note that ap~order (r + k — l)-crown is only defined when 2(r + k -1) S p.

49

C] Vertices that are distance 2 away from 0
O Vertices that are distance 3 away from 0

 

Figure 4.10: Vertices that are distance 2 and 3 away from vertex v0.

Given a vertex vj which is distance 3 away from v0 in an r-crown, the k edge-disjoint paths

joining v0 and vj in an (r + k -— 1)-crown can be given as:

Case 2r — 1 S j S 4r - 5: We construct a set of k edge-disjoint paths by considering two sets
of k vertices that are adjacent to v0 and vj. Since all the vertices adjacent to v0 are odd3
and all the vertices adjacent to Uj are even, by definition of an (r + k — 1)-crown, we have
N (v0) n N (v,-) = 0. However, we have to show that all the k vertices used in N (on) are
distinct and all the k vertices used in N (12,-) are distinct. The construction is divided into
three subcases. A brief overview of each subcase is as follows. In subcase 1, we construct
a set of min(r, k)4 paths. In these min(r, k) paths, v0 is adjacent to odd vertices between5
v0 and v2,_2 and v,- is adjacent to even vertices between v0 and v2,_2. In subcase 2, we

1th I

construct an r + path.

 

3We calla vertex v: odd(even), if i is odd(even).

‘min(r, It) refers to the minimum of r and I:

5’By “between v.- and ”1'" we refer to the vertices on the clockwise ‘Ui-‘Uj path in the spanning cycle of the given graph,
as can be seen in Figure 4.11.

50

In subcase 3, we construct the rest of the k — r — 1 paths. In these paths v0 is adjacent to
v2(,+k_2)_3, v2(,+k_2)_5, . . . , v2(,+k_2)_2(k_,._1)_1. Consider the vertex adjacent to v0 in
the (k—r— I)" path. Since 2(r+k-—2) -2(k—r—- 1) —l > 2r—3, the paths constructed in
subcase 3 would not reuse the odd vertices used in subcase 1. Hence all the selected k vertices
adjacent to v0 are distinct. Similarly in the paths constructed in this subcase, ‘Uj is adjacent to
vp_2, vp_4, . . . ,vp_2(k_,._1). Consider the vertex adjacent to v,- in the (k — r — 1)" path. By
definition of an (r + k - 1)-crown we have, p 2 2(r + k — l) and since r is a positive integer,
we have p — 2(k — r — l) > 2r — 2, which guarantees that the even vertices used in subcase
1 are not reused. Now we are ready to construct a set of k edge-disjoint vo-vj paths of length

at most 3 in an (r + k — 1)-crown.

Subcase 1: For each 0 S l < min(r, k), there exist a path vo,v(2,_2)_2¢-1,v(2,._2)_2,, vj.
By definition v0 is adjacent to v(2,_2)_2,_1. In an r-crown vertex v,- is adjacent to
v2,_2, which implies that in an (r + k - 1)-crown vertex vj is connected to at least
It even vertices before v2,._2. In other words, ‘Uj is connected to v(2,._2)_2,. Note that
when k 2 r, and l = r — 1, the above given path is vo,v_1,vo,vJ-. In this case, we

should consider the edge v0 -v,- as a path.

Subcase 2: If k = r + 1, there exists a path v0, v2(,.+k_2)_1, vj+1, vj. It is easy to see that
the edge (v0, v2(,.+k_2)_1), and (vj+1, vj) exist in a (r + k — 1)-crown. It remains to
show that vj+1 is joined to v2<r+k_2)_1 in an (r + k — 1)-crown. By definition, in an
(r + k — 1)-crown the vertex Uj+1 is joined to all odd vertices in between v04”) and
vu+1)+2(,+k_2)_1. Sincej is positive, 2r — 1 S j S 4r — 5, and k = r + 1, we can
see that v2(,+k_2)_1 is an odd vertex in between v(j+1) and v(j+1)+2(,+k_2)_1. Which

implies, vertex vj+1 is joined to v2(,+k_2)_1.

51

(2r-2)-21- 1
(2r—2)-2l

’ 2r-5
2r-4
2r-3
2r-2

 

 

2(I'+k-2)- 1" . q
2(r+k-2)-3

Figure 4.11: k edge-disjoint paths between v0 and v,- when 2r — l S j S 4r — 5.

   

j+2(r+k-2)-2
o j+2(r+k-2)-l
j+2(r+k-2)

 

j-2(k-2)+1I

j-2(k-l)+l
Figure 4.12: k edge—disjoint paths between v0 and vj when p — 2r + 1 S j S p - 3.

52

Subcase 3: If k > r + 1, there exists a path v0, v(p_2,_2)+2(,+k_2)_1,vp_2¢_2, Uj, fOr each
0 S l < k—r—1.Sincek > r+1,vertexvj isconnectedtovp_21_2i,0 S l <
k — r — 1. Hence, it is enough to show that v0 is adjacent to v(p_2¢_2)+2(,+k_2)_1, for
each 0 S l < k — r -— 1. We know that vertex v0 is adjacent to all odd vertices between
v1 and v2(,+k_2)_1. Note that p — 2l - 2 + 2(r + k — 2) — 1 2 p and since vertex index
operations are taken over modulo p, it remains to show that 1 S 2(r+k—2) —1—2l—2 S

2(r+k—2)-1.Sincek>r+1>2and0Sl<k—3,theaboveinequalityholds.

Figure 4.11 shows a set of k edge-disjoint paths between v0 and vi when k > r.

Case p —- 2r + 1 S j S p — 3: In this case, we consider vertices vU_2I+1), 0 S l < k, which are
adjacent to v,-. From each of the k vertices, traverse through the (r + k — 2)”' chord to reach
a vertex adjacent to v0. Such a set of k edge-disjoint paths can be given as follows. For
each 0 S l < k, v0, v(j_2,+1)+2(,+k_2)_1, vj_2¢+1,v,-. Now, we will show that vertex v0 is
adjacent to vertex v(j_2,+1)+2(,.+k_2)_1. Since, p — 2r + 1 S j S p — 3 and vertex index
operations are taken over modulo p, the vertex v(j_2;+1)+2(,.+k_2)_1 is in between v2k_2¢-3
and v2(,+k_2)_(2,+3). It is easy to see that for all values of l, vertex v0 is adjacent‘to odd
vertices in between v2k_2;_3 and v2<r+k_2)_(2,+3). Since we use the (r + k — 2)“ chord
from each of the k distinct vertices to reach a vertex adjacent to v0, all the vertices used in

N (v0) are distinct.

Figure 4.12 shows a set of k edge—disjoint paths between v0 and vj. Figure 4.13 shows a 5-regular
crown and a set of 3 edge-disjoint paths between vertices v0 and v7 which are distance 3 apart in a

3-regular crown. ‘ Ci

53

 

Figure 4.13: A set of 3 edge-disjoint paths between v0 and v7.

 

Figure 4.14: A C(28, 7).

 

Figure 4.15: C(28, < 3,7,9 >) E f2(C(28,7)).

4.3 Chordal Graphs

Theorem 8 Given non-negative integers p, k, and h, and a three regular chordal graph G (p, h),

wehaveG(p,< 1,3,... ,2k— 1,h,h+2,... ,h+2k >) Efk(C(p,h)).

Proof: By definition,aC(p, h) isaspanning subgraph ofC(p,< 1,3,... ,2k—1,h,h+2,... ,h-i-
2k >). Also, by definition, C(p, < 1,3, . .. ,2k - l,h,h + 2,... ,h + 2k >) has the following

edges,
1. (vi, v(,-+2I_1)), 0 S l S k for any even vertex v,.
2. (v,-, v(,-+,,+2,)), 0 S l < k for any even vertex v,-.
3. (v,-, v(j_2¢+1)), 0 S l S k for any odd vertex v,-.

4. (v,-, rib-4-21)), 0 S l < k for any odd vertex vj.

55

 

 

 

 

 

Destination k edge—disjoint paths

v2 v0,v(h+2i),v(h+2t)-h—2(t—I) 1 S ‘i < k
v0: ‘01 : v2 kth path

vh—I ”0a”(k+2i)iv(h+2i)-2(i+l)+l 0 S i < k

vh+1 vo,v(h+2t),v(h+2i)—2i+1) 0 S 1 < ’6

 

 

 

 

 

 

 

Table 4.1: k edge-disjoint paths to vertices that are distance 2-away from v0.

Due to Theorem 1, it suffices to show that (1) vertices that are distance two apart in a C (p, h)
are joined by k edge—disjoint paths of length at most two, and (2) vertices that are distance three
apart in a C (p, h) are joined by k edge-disjoint paths of length at most three. Since chordal rings
are point symmetric [42], without loss of generality, we assume that our source vertex is v0. First
let us consider vertices that are distance two apart from v0. In a C (P, h) all vertex pairs that are
distance two away from each other are of the form v0 and v2, v0 and vh_1 and, v0 and vh+1. The k
edge-disjoint paths of length at most two for the above three pairs are given in Table 4.1. It is easy

to see that the given k paths are edge (in fact, vertex) disjoint.

Now let us consider the vertices that are distance three apart. Note that, in a C (p, h),all the
pairs of vertices that are distance 3-apart from v0 are odd and of the form (vo,v3), (vo,vh_2),
(vo,vh+2). (”mink—1). ("0.12215“), (vOi’U-z-h)’ (”om-h): (voivz—h) and (vOIUp-3)' The k
edge-disjoint paths of length at most three for the above pairs are given in Table 4.2. By the
definition of a generalized chordal ring, for any vertex, v), that is distance 3 away from v0, we have
N (v0) 0 N (w) = 0. Hence, it is easy to see that the given k paths are edge (in fact, vertex) disjoint.

C]

A C(28, 7) is shown in Figure 4.14. A graph in fk(G(28, 7)) is shown in Figure 4.15. Figures
4.16 and 4.17 show the two edge-disjoint paths of length 3 between vertex pairs 0,15 and 0,19

respectively.

56

 

 

 

 

 

 

 

 

 

 

 

 

 

Destination k edge-disjoint paths
”3 ”0a ”(mm ”(Havana-2)), ”(mo-(h+2(k—2))+(2(k—t)-1) 0 S l < k - 2
”Orvlav2iv3 (k - I)”t path
vo, v3 ’6‘" Path
vh—z v0,vat-1),v(2I—1)—(2h—1),v(2t-1)—(2rc-I)+(h+2(rc—I-I)) 1 S l < k
‘00, ”In vh-l : vii—2 kth path'
vh+2 ”0iv(2l+l)iv(21+l)—(2k—l)iv(2l+l)-(2k-1)+(h+2(k-l)) 1 S l < k
”0: v1 9 122, vii-+2 kth Path
vzh-I 1’0,”(h-+21):”(h+21)—(2k-1)av(h+2l)-—Q.k—l)+(h+2(k—l-l)) 0 S l < k
v2h+1 v0:v(h+2l)rv(h+2l)—(2(k—1)-l)a ”(h+2l)-(2(k—l)—1)+(h+2(k-l—1)) 0 S l < ’6
v-2—h v0, ”(21-1),”Qt—ll—Qwifi-llir”Qt-j—(hHLk-llLHIk-l-IL-l 0 S l < ’6
v—h ”0a”(m—l),v(2l—l)-(h+2(k—1))av(2l-1)—(h+2(k—l))+2(k—l)-l 0 S l < k
v2—h vo,v(2t+1),v(2I+I)—Qt+2(k—I)),v(2I+I)-(h+2ik-1))+2(rc-I)-1 0 S l < k
vp-s v0:”(21—1),v(2l—l)—(h+2(k—l))iv(2(—l)—(h+2(k—l))+(h+2(k—l—2)) 0 S l < k - l
00, vale—g, v(2k—3)—(2k—1), 12.3 = ”11-3 km path

 

Table 4.2: k edge-disjoint paths to vertices that are distance 3-away from v0.

‘\

"
I
p
a
I "
)e'
\
I
"--‘
J-_--:r
I

I
oil-’-

 

Figure 4.16: Edge disjoint paths between 0 and 15 in 3 C(28, < 3, 7, 9 >).

 

 

\
_‘-—
St- ‘

 

Figure 4.17: Edge disjoint paths between 0 and 19 in a C(28, < 3, 7, 9 >).

4.4 n-ary 2-cube

Theorem 9 Given a n-ary 2-cube, my D, and a non-negative integer k < n, we show that there

exist a (2k + 2)-regular graph in HAD).

First we will present the construction of a (2k + 2)-regular graph. We partition the edge set

f

Proo

of the given n-ary 2-cube into n cycles of size 2n each. Using the solution for Can, we construct

a k-edge distance preserving graph for each of the cycles. We will then show that the linedisjoint

sum of these graphs is (2k + 2)-regular and k-edge distance preserving with respect to the given

n-ary 2-cube. Note that, the edges are partitioned in such a way that the distance between any two

vertices in any partition is same as the distance between them in the original graph D.

58

The n cycles of size 2n are given as follows:

0th cycle: (0,0), (1,0), (1,1), (2, 1), (2,2),. . . ,(n — 1,n — 2), (n — 1,n — 1),
(0,n — 1),(0, 0).

1st cycle: (1,0), (2,0), (2,1), (3,1), (3,2),.. . ,(n - 1,n — 2), (0,n — 2), (0,n — 1),
(1,n —1),(1,0).

2"" cycle: (i,0),(i+1,0),(i+1,1),(i+ 2,1)... ,(n —1,n — i — 1), (0,n — i — 1),

(01” — i): (1,“. _ i): ' ° 1(1)” _ 1): (1:0)
(n _1)th CYCIC: (n _1a0)i(0:0):(0r 1): (131)1(112) ° ' ' 1(n - 2r" - 2): (Tl _ 2:" _1)r

(n— 1,n- 1),(n- 1,0).

Given a vertex (i, j) it belongs to (i — j)“ and (i — j — I)“ cycles6. Similarly given any edge

)‘h cycle, where b=1 if i1 = i2. It is easy to

01 17, say (Unit), (12,172)) it belongs to (it - .71 - 5
see that each of the partitions are mutually edge disjoint. Figure 4.18 shows cycle 0 and eyele 5 in

a 8-ary 2—cube.

Now we will present some notation that will be useful in the remaining part of the proof. We
label a vertex (i, j) even if (i + j) is even and odd otherwise7. Two cycles, say p and q, aresaid to
be neighbors if Ip — qI = 1. Note that in any two neighboring cycles, we have either the same set of

even vertices or the same set of odd vertices.

For each cycle we construct a (k + 1)-crown with even vertices in one partition and odd vertices

in another partition. We will name the edges of the resulting (k + 1)-crown as forward or backward

 

6All the vertex indices and cycle numbers are taken over modulo n.
7By the way we partitioned, each cycle contains an alternative sequence of even and odd vertices.

59

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

T” 0 th Cycle —’ 5 th Cycle

Figure 4.18: 0‘” cycle and 5"I cycle in a 8x8 torus.

 

Figure 4.19: A 4-crown (k = 3) for the 4‘” cycle in a 8x8 torus.

| " 5th Cycle
(5.0)

 

3rd PC from (4.6)

2116 PC from (4.6)
lst PC from (4.6)

0th BC from (3.6)

lst BC from (3.6)
20d BC from (3.6)

 

3rd BC from (3.6)

 

Figure 4.20: A 4-crown (k = 3) for the 5‘“ cycle in a 8x8 torus.

chord as follows:

If (i,j) is even ((i,j), (i + 1,j + l — 1)) 0 S l S k lt" PC from (i,j) in cycle (i — j).
((i,j),(i+l—1,j+l)) OSISk l‘hFCfrom(i,j)incycle(i-j—1).
If (i,j) is odd ((i,j), (i — l + 1,j — l)) 0 SIS k l"‘ BC from (i,j) in cycle (1' — j).

((i,j),(i—l,j—l+1)) OSlSk l"‘BCfrom(i,j)incycle(i—j—1).

Note that in an (i — j)"‘ cycle, the 1‘” PC from (i, j) can also be called 1‘” BC from (i + l, j +
l — 1). Figures 4.19 and 4.20 show the 4th and 5th cycles in a 8-ary 2-cube and the corresponding
4-crowns. These two neighboring cycles have the same set of odd vertices. Figure 4.20 also shows
the PCs and BCs from vertices (4, 6) and (3, 6), respectively. By construction, an even and odd
vertex pair can belong to no more than one cycle. And since a (k + l)-crown is constructed by
connecting even vertices and odd vertices, it is easy to see that the (k + 1)-crowns are mutually
edge disjoint. Since each vertex belongs to two cycles, the degree of the resulting line disjoint union

of the (k + 1)-crowns is a (2k + 2)-regular graph.

61

 

= (i-j-l)th cycle

 

 

(i-IJH) 5 _ (i+i,j+l)

 

 

I ............. . ............. o (i+2,j)
.............
(l+l,j-1)
i
(i,j-2)

Figure 4.21: Vertices that are distance 2 away from (i, j) in n-ary 2-cube.

In the remaining part of the proof, we will Show that the above constructed graph is k-edge
distance preserving with respect to n-ary 2-cube. Using Theorem 1, it is enough to show that there
are k-edge disjoint paths of length at most 2 and 3 between vertices that are distance 2 and 3 apart,
respectively. Since a n-ary 2-cube is point symmetric, without loss of generality, we assume that

(i, j) is even.

As shown in Figure 4.21, vertex (i, j) has the following vertices that are distance 2 away: (i, j +
2),(i+1,j+1),(i+2,j),(i+1,j—1),(i,j -2),(i— 1,j — 1),(i —2,j) and (i— 1,j+ 1).
By the way we partitioned, vertices (i — 1, j - 1), (i, j) and (i + 1, j + I) belong to (i -— j — 1)th
cycle and the vertices (i — 1, j — 1) and (i, j) are distance two apart in the cycle. Similarly, vertices
(i, j) and (i + 1, j + 1) are also distance two apart in the same cycle. Hence, by construction, there
are k-edge disjoint paths of length at most 2. Since a n-ary 2-cube is a point symmetric graph it is
enough to Show that there are k-edge disjoint paths from (i, j) to each of (i + 2, j),(i + 1, j — 1)

and (i,j - 2).

Between (i, j) and (i + 2, j), we Show that there are k-edge disjoint paths of length two by

considering two neighboring cycles containing (i, j) and (i + 2, j), respectively. Consider the

62

 

Destination Cycles Common vertices
(i+2,j) (i—j)and(i—j+l) (i+l,j+l-1),lSlSk

(i+l,j+1) (i—j)and(i—j+1) (i+l,j+l—l),0Sl<k
(i,j—2) (i-j)and(i—j+1) (i+l,j+l—l),0Sl<k

 

 

 

 

 

 

 

 

 

Table 4.3: k-edge disjoint paths to vertices that distance two away from (i, j).

 

 

 

 

 

 

 

 

(0+3)
9
(i-l.j+2) (i+l,j+2)
9 ............. 9 ............. 0
; . = (i-j-l)th cycle
(i-2,)+1) (i+2,j+l)
9 ............. ; ;
E = (i-j)th cycle
“-3,” . ............. . ,,,,,,,,,,,,, 3 ............ . ............. . (i+3,j)
= (ii) 3
: . ............ ‘P ............. .
(i-2J-i) (i+2,j-l)
I ............. ............. ;
(i-lJ-Z) g (i+l,j-2)
3
(i,j-3)

Figure 4.22: Vertices that are distance 3 away from (i, j) in n-ary 2-cube.

(i — j )‘h cycle and (i - j + 1)“ cycle. It is easy to see that both of these cycles contain the same
set of odd vertices. Similarly, the neighborhood of N (i, j) in the (i - j)"I cycle is (i + l, j +l — 1),
0 S l S k. The neighborhood ofN(i+2,j) inthe (i — j + 1)"I cycle is (i+l+l,j+l), 0 SIS k.
Hence, the k common vertices are (i + l,j +l — l), 1 S l S k. A similar proof can be given for the
k-edge disjoint paths from (i, j) to (i + 1, j — 1) and (i, j — 2). Table 4.3 summarizes the k-edge
disjoint paths that are distance 2 away from (i, j).

Now we will consider the vertices that are distance 3 away. As shown in Figure 4.22, the vertex

(i,j)isdistance3awayfrom(i,j+3),(i+1,j+2),(i+2,j+1),(i+3,j),(i+2,j—1),(i+

63

 

   
  
  

 

 

 

 

 

(i+l.j) (i-k+3,j-k+l)
(k-l)st BC
lst PC ‘ .................. (l+2,j+l) .................. , k m FC
-1 B
2nd m ‘ ............... (k )8! C ............... ’ (k-l)st FC
III! E ‘ '''' ""5 .(i+l.j+l'l) 5"" """ ’ (k’l+l)5t PC
(i,j) ' (k-l )st BC ‘ (i+3,j)
(k- 1) st FC ‘ ............... (i+k-l'j+k-2) ............... ’ 2nd PC
' k-l 1 BC
k 111 PC <1 .................. (i+k.j+k- I) ( )8 .................. a. lst FC
' (k-l )st BC

Figure 4.23: k-edge disjoint paths between (i, j) and (i + 3, j) in a n-ary 2-cube.

1,j—2),(i,j—3),(i—l,j—2),(j—2,j—1),(i—3,j),(i—2,j +1), and (i—l,j+2). Vertices
(i — 2,j — 1) and (i + 1,j + 2) belong to (i —j - 1)”' cycle and hence by construction we have
k-edge disjoint paths of length at most 3. Similarly, vertices (i — 1, j — 2) and (i + 2, j + I) belong
to (i — j) cycle and by construction we have k-edge disjoint paths of length at most 3. Since a n-ary
2-cube is a point symmetric graph, it is enough to Show that there are k-edge disjoint paths from
(i,j) toeach of(i +3,j),(i +2,j — 1),(i+1,j— 2), and (i,j — 3).

For the k-edge disjoint paths between (i, j) and (i + 3, j ), consider the following three cycles.
(i—j), (i—j+1),and (i-j+2). Notethat (i,j) and (i+3,j) arein (i —j)"' and (i —j +2)th
cycles, respectively. And the cycle (i - j + 1) connects the odd vertices of (i — j )"I cycle to the
even vertices of (i - j + 2)“ cycle. The k-edge disjoint paths can be constructed as follows. From
(i, j) take the lt", l S l S k, forward chord in cycle (i — j) to reach an odd vertex. From each odd
vertex, take the (k — 1)“ backward chord in cycle (i — j + 1) to reach an even vertex. From each
such even vertex take the (k — l + 1)“ chord in cycle (i — j + 2) to reach (i + 3, j). Figure 4.23
shows the k-edge disjoint paths between (i, j) and (i + 3, j).

To see that the above given k-paths are edge disjoint (in fact, vertex disjoint), consider the

vertices { (i + l, j + l — 1)| 1 S l S k} Q N [(i, j)]—these vertices are all distinct by construction.

(i+l.j) (i-k+2,j-k)
kmBC

 

   
  
  

 

 

 

 

 

lst FC g .................. (i+2,j+l) .................. p k th FC
mBC
211d FC ‘ ............... k ............... x» (k-l)$t FC
l th FC < """ ° (i+l,j+l-l) ----- > (k-l+1)sl FC
(u) ' kmBC dawn
(k- I) st FC ‘ ............... (i+k-l.j+k-2) ............... ’ 2nd FC
' kmBC
k th FC Q .................. (i+k‘j+k-l) .................. p lst PC
' kmBC

Figure 4.24: k-edge disjoint paths between (i, j) and (i + 2, j — 1) in a n-ary 2-cube.

 

     
  
    
   
 
  
  

  
 
  
  
 

 

 

 

 

(i+l.j) (i-k+2,j-k)
kmBC
lst FC ‘, .................. (i+2,j+ l) (1'k‘1' 3.j-k+ l) .................. g, (It-”Si FC
2nd PC ‘ ............... k [h BC ............... p (k_2) "1 FC
1 ‘1‘ PC ‘ """ ' (i+l,j+l-l) (i+l-k+l,i-hl-k-l) “““ ’ (Wm PC
(i,j) ' k th BC ' (”1,j-z)
(k-l) 81 FC ‘ ............... (i+k- 1sj+k' 2) (i,j-2) ............... > lst FC
' kmBC RT
1: m FC 4 .................. (i+k,j+l(-l) (i+l,j-l) ................... > 0 th FC
' kmBC '

Figure 4.25: k-edge disjoint paths between (i, j) and (i + 1, j - 2) in a n-ary 2-cube.

(ii-l) (i-k-l-lJ-k-l)

 

   
  
    
  

 

 

 

 

kmBC
0 1h FC ¢ .................. (1+1J) (i-k+2,j-l() .................. p (it-l )st FC
1 3'. FC ¢ ............... k m BC ............... , (k_2) th FC
lmFC ‘ """ (nuns) anhyhhm """ ’ 9+”mFC
up " kmBC ' as»
(k_2) St FC ( ............... (i+k-l’j+k-2) (i-l'j-3) ............... p 18‘ FC
' kmBC '
(k_l) Ill Peg .................. (i+kJ-i'k-l) (Id-2) .................. D 0 01 PC
' kmBC '

Figure 4.26: k-edge disjoint paths between (i, j) and (i, j — 3) in a n—ary 2-cube.

 

Even Vertex

Figure 4.27: 8—regular graph that belongs to f3(n-ary 2-cube).

Since we took the (k — 1)“ BC from each vertex in the above set, it is easy to see that the vertices
{(i + l — k + 2,j + l — k)I 1 S l S k} are distinct. A similar proofcan be given to vertices
(i + 2,j — 1), (i + 1,j - 2) and (i,j — 3), which are distance 3 away from (i,j). Table 4.4 and
Figures 4.24-4.26 summarize the k-edge disjoint paths to vertices that are distance 3 away from

(M)- D

Figure 4.27 shows the part of a graph that is 3-edge distance preserving with respect to an
infinite torus. In this chapter we presented distance preserving graphs with respect to cycles, crowns,

chordal graphs, and n-ary 2-cubes. In the next chapter we present a polynomial algorithm that can

66

 

 

 

 

 

 

 

 

 

 

 

 

 

Source Next odd vertex is Next even vertex is Destination

vertex inCycle (i + j + l) in Cycle (i+j +2) vertex

(i,j) (i+l,j+l—1) (i+l—k+2,j+l—k) (i+3,j), 1<l<k
takel‘hFC take(k—l)"tBC take(k—l+1)t”FC

(i,j) (i+l,j+l—1) (i+l—k+1,j+l—k—1) (t+2,j—1), 1<i<k
takel‘hFC takek‘hBC take(k—l+l)t”FC

(i,j) (i+l,j+l-1) (z’+i—k+1,j+i—k—1) (i+l,j—2), 1<t<k
take l‘h FC take kt" BC take (ls—l)"I FC

(i,j) (i+l,j+l—1) (i+l—k+2,j+l—k) (i,j—3), 0Sl<k
takel‘hFC takek‘hBC take(k—l—1)"’FC

 

 

Table 4.4: k-edge disjoint paths to vertices that are distance 3 away from (i, j).

find the maximum k, when a graph G and a spanning subgraph D is given.

 

 

 

Chapter 5

An Algorithm To Find k Given D and G

It is well known that the problem of finding the maximum number of edge-disjoint paths of bounded
length, say K, between a pair of vertices in a graph is NP-hard [46]. However, the problem is
solvable in polynomial time when K S 5 [46]. Hence, given a graph G and a spanning subgraph
D, Theorem 1 and the polynomial algorithm in [46] can be used to determine if G belongs to .7), (D)

for some non-negative integer k. Details of such an algorithm are presented in this chapter.

We present an algorithm which takes graphs D and G as input and computes the maximum
possible value k such that G 6 fk(D). Since the subgraph isomorphism problem is NP-complete
[47], we assume that the given graph G contains D as a spanning subgraph. The algorithm Find_k

is given in Figure 5.2. An outline of the algorithm is presented here.

In general, the max flow problem can be used to compute the maximum number of edge—disjoint
paths joining two vertices in a graph [48]. However, a similar technique cannot be used to find the
maximum number of edge-disjoint paths of bounded length. For example, consider graphs I and J
in Figure 5.1(a) and 5.1(b), respectively. We are interested in the maximum number of edge-disjoint
u-v paths of length at most 3 in I and J. Let us use the max flow approach to compute the edge-
disjoint paths of length at most 3 in the given graph. For graph I, if u, 2:, v is selected as the first u-v

67

68

path then the only remaining edge-disjoint path connecting u and v is u, w, 2:, y, v which is of length
4. However, there are two edge-disjoint paths of length at most 3 namely, u, w, 2:, v and u, 2:, y, v.
Similarly in J, if u,w,.v, v is selected as the first path then there is no other edge-disjoint path
connecting u and v. But there are 2 edge-disjoint paths of length at most 3 between u and v in J.
Hence the well known maximum flow algorithm cannot give the maximum number of edge—disjoint

paths of bounded lenght, even for small values of K.

5.1 Outline of the Algorithm

Due to Theorem 1, k can be computed by using only non-adjacent vertices that are at most distance
3 apart in D. Step 1 and Step 2 of the algorithm considers every pair of non-adjacent vertices u and
v in D, with dD(u, v) = 2 and dp(u, v) = 3, respectively. In each step, the algorithm computes the
minimum of the maximum number of edge-disjoint paths. When dp(u, v) = 2, it is easy to see that
INGIu] n NG[v]| represent the maximum number of edge-disjoint u-v paths in G of length at most
2. In Step 1, k is set to the minimum value of all such u,v pairs. Now, we explain how to compute
the maximum number of edge—disjoint paths in G between vertices that are distance 3 apart in D.
First we present some useful properties of edge-disjoint u-v paths of length at most 3 in G. Let
us denote by L, a set of edge—disjoint u-v paths of length at most 3 in G. Let L1 and L2 be any two

paths in [2.
Property 9 |(V(L1) n V(L2))\{'U:v}I S 1-

Proof: Let |(V(L1) n V(L2))\{u,v}| > 1. This implies that both L1 and L2 are of length 3.
Let L1 = u, w, x, v. Since the graph G is a Simple graph we have only one choice for another
edge-disjoint u-v path using vertices w and 1:. That is, L2 = u, 2:, w, 12. But then L1 and L2 share a

common edge (w, x)—a contradiction. D

69

W
u y
I] V
X
W V X
(a) Graph I (b) Graph J
W W

(0) Graph I ’ ((1) Graph J’

Figure 5.1: Graphs I and J and their corresponding I ’ and J’.

Property 10 If(V(L1)0 V(L2))\{usv} r 0 the" |E(L1)| = |E(L2)| = 3-4150. ‘fIE(LI)I = 2.

thenfor any other L; 6 [3, we have (V(Ll) fl V(L2)) = 0.

Proof: Assume otherwise and without loss of generality, let L1 be a path of length 2; And let
{V(Ll) r) V(L2)}\{u,v} = {w}. Since |E(L1)I = 2 we have both (it, w) and (w, v) E E(Ll).
Since w E V(L2) we must have either (u, w) E E(L2) or (v,w) E E(L2). Implying that L1 and

L2 are not edge-disjoint—a contradiction. - Ci

Property 11 lf(V(L1) F) V(L2))\{u,v} = {w} Then w E {Na(u) n Na(v)}.

Proof: Since L1 and L2 are edge-disjoint w cannot be adjacent to u (similarly to v) in both L1 and

L2. Hence, if (u, w) E E(Ll) then (v,w) E E(L2). This implies w E {Nc(u) n Na(v)}. D

70

Property 12 Any vertex in w E V(G)\{u, v} can at most be in two paths in [1. Further; any such

vertex is adjacent to u in one path and adjacent to v in the other path.

Proof: Since all the paths in L are of length at most 3, any intermediate vertex, w, in any path in
.C has only two choices. Either w must be adjacent to u or to v. Hence vertex w can be adjacent
to u in one path and to v in another path. That is L1 = (u,w,:r,v), L2 = (u,y,w,v) for some
it E V(G)\{u,vl B
Our algorithm computes the maximum number of edge—disjoint paths of length at most 3 by count-
ing the number of vertex—disjoint paths in a new bipartite graph G’ which is constructed from
H = G [Ng[u] U Ng[v]]. Before we explain the construction of G’ notice that the maximum
number of edge-disjoint u-v paths of length at most 3 in graphs G and H are equal this is because,
all the vertices used in any u-v path in G of length at most 3 must belong to Na[u] U Ng[v]. To
avoid some special cases we assume that (u, v) ¢ E(G); if (u, v) E E(G) then k is incremented by
1 in the last step of the algorithm Find_k.

We now construct a bipartite graph G’ from H with V(G’) = V(H) U {w’lfor every w E
N H (u) n NH(v)}. In other words, for every vertex w in NH (u) n NH(v) we have two copies,
w and w’, in G’. Also, w and w’ are referred first copy vertex and second copy vertex, re-
spectively. The edge set of G’ is given as follows. For each w E N H (u) n NH (v) we have,
{(u, w), (w, w’), (v, w’)} E E(G’) (Figure 5.3); And any edge (w, :r) E E(H) is replaced in G’ by
(2:,w’) and (w, z’), ifs: E NH(u) n NH(v) (Figure 5.4) and (2:,w’), ifs: E NH(u)\NH(v)(Figure
5.5) and (w, 2:), ifx E NH(v)\NH (u)(Figure 5.6).

For every w ¢ Ng(u) n Ng(v), if (u, w) E E(H) then (u, w) E E(G’) and if (v,w) E E(H)

then (v, w) E E (G’ ). The following observations are immediate from the construction of G’.

1. Any first copy vertex is always adjacent to u in G’ and any second copy vertex is always

71

adjacent to v in G’.
2. The first and second copies of a vertex w E N ”(u) r) N ”(v) are always connected in G’.
3. If (u,w) E E(H), for some w E V(H), then (u,w) E E(G’).
4. If (w’,v) E E(G’) then w E NH(u) fl NH(v). (Otherwise, w’ ¢ V(G’)).
5. (w,v) E E(G’), ifand only ifw E NH(v)\NH(u).

6. If (w,:l:) E E(H) and if both w and z ¢ Na(v) then (w,:l:) ¢ E(G’). Similarly, If (w,:l:) E

E(H) and if both w and a: 9! Ng(u) then (w, 2:) ¢ E(G’).
7. G’ is a bipartite graph.

Such a G’ for the graphs I and J is given in 5.1(c) and 5.1(d), respectively. We claim that the
maximum number of edge-disjoint paths of length at most 3 in H is equal to the maximum number

of vertex-disjoint paths in G’. A proof for the above claim is given in Theorem 10.

Theorem 10 Given a graph D and a graph G having D as a spanning subgraph the algorithm

FindJc computes the maximum k such that G E fk(D).

Proof: In this proof we show that every pair of non-adjacent vertices u and v are joined in G by
at least k edge-disjoint paths; Also we show that such a k is maximum. In other words, for no
other k’ > k we have G e 17),: (D). By Theorem 1, we know that such a k is the minimum of the
maximum number of edge—disjoint u-v paths between every pair of non-adjacent vertices u and v
with dD(u, v) S 3.

After the completion of Step 1, it is clear that k will hold minimum of the maximum number of
edge-disjoint paths in G between every pair of vertices u and v with dD(u, v) = 2.

As mentioned earlier, to compute the maximum number of edge-disjoint paths between a pair

of non-adjacent vertices u and v with d D (u, v) = 3, the step 2 of the algorithm constructs a graph

72

Algorithm: Find_k

Input: Graphs G and D (D is a spanning subgraph of G).
Output: Maximum k such that G E fk(D).

Step 1: k = min {INCIuI n Na[v]| for all u and v with dp(u, v) = 2}.

Step 2: For every pair of vertices u and v with dp(u, v) = 3

Construct a graph G’ with
V(G’) = {NGIUI U Nah)” U {w’l for each w E Nc(’u.) r) N0(‘U)}.
The edge set E(G’) is constructed as follows:

For each w 6 Ng(u) n Ng(v)
(u, w), (w,w’), (w’,v) E E(G’)
End
For each w E Nc(u) r) Nah!)
If (w,:l:) E E(G) Then
Case: 1: a: E Na(v) n Na(u)
(wsx'), (aw/I E E(G')
Case: 2: :L‘ E Na(u)\NG(v)
(w,w’) 6 E(G’)
Case: 3: a: E Na(v)\Ng(u)
(w, 2:) E E(G’)
End
For each w ¢ Ng(u) r) N002)
If (u,w) E E(H) Then
(u, w) E E(G’)
If (v,w) E E(H) Then
(v,w) E E(G’)
End
End

If (u,v) 6 E(G) Then

k (— min(k, size of the max matching of (G’ — {u, v}) + 1).
Else

k (— min(k, size of the max matching of (G’ — {u, v})).

End

Figure 5.2: Algorithm for finding max k.

A
v

W V II W

 

<1)

:0
so

Figure 5.3: Graph H and its G’.

73

w w w’
’<I>v =<X>v
x x x‘

Figure 5.4: Case 1 of the Algorithm. G and the resulting G’.

X X
”V ”v
W W W.

Figure 5.5: Case 2 of the Algorithm. G and the resulting G’.

G’ from H = G [Na [u] UNG [v]] By construction, G’ is a bipartite graph; Also, vertex u is adjacent
to all vertices in one partition of V(G’) — {v}. Similarly, vertex v is adjacent to all vertices in
one partition of V(G’) - {u}. It is known that the size of the maximum matching in the bipartite
graph G’ — {u, v} is equal to the maximum number of vertex-disjoint paths between it and v in G’
[48]. Further, any such path is of length 3. In the remaining part of the proof we will show that
the maximum number of edge-disjoint u-v paths of length at most 3 in H is equal to the maximum
number of vertex-disjoint u-v paths in G’.

Let L = {L1,L2, . .. ,LI} and M = {M1,M2, . .. ,Mm} be the set of edge-disjoint paths of
length at most 3 between u and v in H and G’, respectively. It suffices to show that l S 1m and
m S 1.

Using the properties mentioned in the outline of the algorithm, we will show that l S m. For

w w w'

Figure 5.6: Case 3 of the Algorithm. G and the resulting G’.

74

each L,- in L,

CaseLi = u,w,v we have M,- = u,w,w’,v.
Since E(L,) = 2 the vertex w cannot be used in any other u-v path in L (Property 9). Hence
the vertices w and w’ in the corresponding path M,- = u, w, w’, v, are not used by any other

path in M. Hence M,- is internally vertex-disjoint with any other path in M.
Case L, = u, w, 2:, v : Then we have two possibilities.

Subcase a: E NH(u) we have M,- = (u,w,cc’,v).
In this case, both a: E NH(u) n NH(v). By construction we have x’ E V(G’) and
(:c’,v) 6 E(G’). Also, since (w,:c) E E(H), we have (w, x’) E E(G’). Hence the path
M,- given above exists in G’. Now, we will prove that M,- is internally vertex-disjoint
with any other path in M. Assume otherwise and let V(Mg) r) V(Mj) = 0, for some
i 75 j. We have (u, w) ¢ Mj because (u, w) ¢ L,- for any LJ- 6 L. Similarly, (:c",v) ¢
M,- because (x,v) ¢ L,- for any LJ- 6 L. In such a case, at least (u, rc’) E E(Mj) or
(w, v) E E(Mj). But (u, :1." ) ¢ E(Mj) because in G’, by construction, no second copy
vertex is adjacent to u. If (w, v) 6 E(Mj) then the edge (w,v) E E(G’) and E(H),

which implies w ¢ N H(u)—a contradiction, because (u, w) E L,- implies w E N H (u).

Subcase x ¢ NH(u) we have M; = (u,w,x,v).
Since z ¢ NH(u) and (2:, v) E E(H), we have edge (2:, v) e G’. Hence it is easy to see
that path M,- exists in G’. Now, we will prove that M; is intemaliy vertex-disjoint with
any other path in M. Assume that there exists another path M j E M, for some i 76 j,
such that V(Mg) nV(MJ-) 94 0. With out loss of generality, let w E V(M;)nV(M,-). In
this case, either (u,w) 6 Mj or (w,v) E M). If(u,:c) 6 M,- then (u, 2:) E Lj, implying

that x E N H(u)—a contradiction. If (w, v) E Mj then this implies that w 5! N H.(u)—a

75

contradiction, because (u, w) E L,- implies w E N ”(u).

76

Now we will show that m S l by constructing a set L of edge-disjoint paths in H. We denote
by copy(X) the original vertex in H; that is copy(X) = 2: whether X = 2: or 2’. For each M.- E M
we construct a path in H, say Lg, using the vertices in Mg. For each M,- = u,w,sc’,v E M,
if there exists another path Mj = u,2:,w’,v then L,- = u,w,v and Lj = u,2:,v ; Otherwise,
L,- = u,w,copy(X),v. Ifw = copy(X) then L,- = u,w,v. It is easy to see that any edge used in
the resulting u-v path exist in E(H).

Now we will prove that the set of paths L constructed from M are edge-disjoint. As-
sume otherwise and let E(Li) Fl E(Lj) sé (II, for some L,- and L7 in L. Note that both L,-
and L,- are of length three. Otherwise, if L,- = u, w,v then either (u,w,w’,v) E 1M or
{(u,w,x’,v), (u,w,w’,v)} Q M and w or w’ cannot be used by any other path in M. Hence,
vertex w is used by at mot one path in L. Without loss generality, let L,- = u, w, 2:, v. Notice that
these two paths cannot share the edge (u, w) or (w, 2:) because M,- is internally vertex—disjoint
with any other path in M. Hence, E(Li) n E(Lj) = {(2:, v)}. If (2:, v) belongs to two paths in L
then the first copy of vertex 2: is adjacent to v in one path in M, say M5. And the second copy of
vertex 2: is adjacent to v to M j. But from the construction of G’ only second copy is adjacent to v.

Therefore, (2:, v) E E(G’); hence (2:, v) E E(M,)—a contradiction. . Ci

Chapter 6

Conclusions

In this dissertation, we introduced a new family of fault-tolerant graphs called distance preserving
graphs. We studied some properties of distance preserving graphs and a result that can be used to
characterize distance preserving graphs is presented. For designing distance preserving graphs we
considered two design models with different optimality criteria Designs in the first model minimize
the overall redundancy. The second model restricts the designs to regular fault-tolerant topologies
with minimum regularity. For both of the design models, we present lower and upper bounds and

Show that the given bounds are tight.

Our focus was mainly on designs based on Model 2. Our solutions include fault-tolerant designs
with respect to cycles, crowns, chordal rings, and n-ary 2-cubes. In particular, we prove that our
designs are optimal when D = 0,, and k S g. We have also shown that the distance between
adjacent vertices, upon edge removal, is bounded by a constant. Finally, given a graph G and a
spanning subgraph D, we present a polynomial algorithm that can be used to find the maximum k
such that G E fk(D).

The results presented in this dissertation can be used in designing fault-tolerant communication

networks in which distance between communicating nodes is critical.

77

m
6.1 Future Work

The given fault-tolerant designs for crowns, chordal rings, and n-ary 2-cubes are optimal for lower
values of k. However, we believe that the given constructions are optimal for any k. Thus, we state

the following conjectures.

Conjecture 1 For any p-order r-crown, there does not exist an i-regular p-order graph G E

fk(r-crown),for anyi < r + k —— 1.

Conjecture 2 For any C (p, h), there does not exist an i-regular graph G E .7), (r — crown), for

any
1. i<2k+l,tfh22k.

2. t<k+[%]+l.ifh<2k.

Conjecture 3 For any n-ary 2-cube, there does not exist an i-regular graph G E f), (n-ary 2-cube),

for anyi < 2k + 2.

The fault-tolerant design given for C, when k S g, is optimal for Model 2 designs. We believe that

the same fault-tolerant graph is optimal even for Model 1 designs. Formally,
Conjecture 4 For any p-order cycle, Cp, there does not exist a Kigali — 1 size graph G E fk(Gp).

Regular topologies seem to be popular for their simplicity and scalability in designing fault-
tolerant CNS [18, 20]. However, fault-tolerant designs involving minimum redundancy prevail in
CNS where the cost of the CN is an important factor. Optimal designs for Model 1 need to be studied
in more detail.

Throughout the dissertation, we studied deterministic measures of fault-tolerance. The founda-

tions laid out in this dissertation can be used to investigate probabilistic measures of fault-tolerance.

79

The fault-tolerant designs given for n-ary 2-cubes are based on partitioning the edge set of the
n-ary 2—cube into n partitions, where each partition is a cycle of order 2n. A similar technique can

be used to develop a framework in designing topologies for any given arbitrary graph.

Bibliography

[1] A. L. DeCegama, The Technology of Parallel Processing, vol. 1. Prentice Hall, 1989.

[2] S. Dutt and J. P. Hayes, “Some practical issues in the design of fault-tolerant multiprocessors,”

IEEE Transactions on Computers, vol. 41, pp. 588—598, May 1992.
[3] M. J. Quinn, Designing Efficient Algorithms for Parallel Computers. McGraw-Hill, 1987.

[4] J. P. Hayes, “A graph model for fault-tolerant computing systems,” IEEE Transactions on

Computers, vol. 25, pp. 875—884, Sept. 1976.

[5] C.-L. Kwan and S. Toida, “Optimal fault-tolerant realizations of some classes of hierarchical
tree systems,” The 11’” lntemational Conference on Fault-Tolerant Computing, pp. 176—178,

1981.

[6] C. S. Raghavendra, A. Avizienis, and M. D. Ercegovac, “Fault tolerant in binary tree architec-

ture,” IEEE Transactions on Computers, vol. 33, pp. 568—571, June 1984.

[7] M. B. Lowrie and W. K. Fuchs, “Reconfigurable tree architectures using subtree oriented fault

tolerance,” IEEE Transactions on Computers, vol. 36, pp. 1172—1183, Oct. 1987.

[8] S. Dutt and J. P. Hayes, “On designing and reconfiguring strategies for k-fault tolerant tree
architectures,” IEEE Transactions on Computers, vol. 39, pp. 490—503, Apr. 1990.

80

81

[9] J. Bruck, R. Cypher, and C.-T. Ho, “On the construction of fault-tolerant cube-connected cy-

cles networks,” in Proceedings of the I 991 lntemational Conference on Parallel Processing,

vol. 1, pp. 692—693, 1991.

[10] J. Bruck, R. Cypher, and C.-T. Ho, “Fault-tolerant meshes with minimal numbers of spares,”
in Proceedings of the 1991 Symposium on Parallel and Distributed Processing, pp. 288-295,

1991.

[11] J. Bruck, R. Cypher, and C.-T. Ho, “Fault-tolerant de Bruijn and shuffle-exchange networks.”

Unpublished Document.

[12] F. Boesch, “Synthesis of reliable networks - a survey," IEEE Transactions on Reliability,

vol. 35, pp. 240—246, Aug. 1986.

[13] A.-H. Esfahanian, “Generalized measures of fault-tolerance with application to n-cube net-

works,” IEEE Transactions on Computers, vol. 38, pp. 1586—1591, Nov. 1989.

[14] D. K. Pradhan and S. M. Reddy, “A fault-tolerant communication architecture for distributed

systems,” IEEE Transactions on Computers, vol. 31, pp. 863-869, Sept. 1982.
[15] F. Harary, Graph Theory. Addison-Wesley Publishing Company, 1968.

[16] M. 0. Ball, “Complexity of network reliability computation,” NETWORKS, vol. 10, pp. 153-

165, 1980.

[17] R. J. Dawson and A. A. Farrag, “Fault-tolerant extensions of star networks,” NETWORKS,

vol. 21. pp. 373-385, 1991.

[18] D. V. Chudnovsky, G. V. Chudnovsky, and M. M. Denneau, “Regular graphs with small diam-
eter as models for interconnection networks,” in Proceedings of the 3"“ International Confer-

ence on Supercomputing, vol. 3, pp. 232—239, 1988.

82

[19] W. J. Dally, “Performance analysis of k-ary n-cube interconnection networks,” IEEE Transac-

tions on Computers, vol. 39, pp. 775—785, June 1990.

[20] G. Zimmerman and A.-H. Esfahanian, “Chordal rings as fault-tolerant loops,” Journal of Dis-

crete Applied Mathematics, vol. 99, pp. 563—573, Dec. 1992.

[21] F. Harary and J. P. Hayes, “Edge fault tolerance in graphs,” NETWORKS, vol. 23, pp. 135—142,

1993.

[22] F. Harary, “The maximum connectivity of a graph,” Proceedings of National Academy of Sci-

ences, vol. 48, pp. 1142-1146, 1962.

[23] K. Vijayan and U. S. R. Murty, “On accessibility in graphs,” Sankhya, Series A, vol. 26,

pp. 299—302, 1965.
[24] B. Bollobas, Extremal Graph Theory. Academic Press, 1978.

[25] F. R. K. Chung, “Graphs with small diameter after edge deletion,” Discrete Applied Mathe-

matics, vol. 37-38, pp. 73-84, 1992.

[26] K. P. Eswaran and E. Tarjan, “Augmentation problems,” SIAM Journal of Computing, vol. 5,

pp. 653—665, Dec. 1976.

[27] H. Whitney, “Congruent graphs and the connectivity of graphs,” American Journal of Mathe-

matics, vol. 54, pp. 150—168, 1932.

[28] F. Boesch and R. Tindell, “Circulants and their connectivities,” Journal of Graph Theory,

vol. 8, pp. 487—499, 1984.

[29] A. Rosenthal and A. Goldner, “Smallest augmentations to biconnect a graph,” SIAM Journal

of Computing, vol. 6, pp. 55—66, 1977.

83

[30] T. Watanabe and A. Nakamura, “A smallest augmentation to 3-connect a graph,” Discrete

Applied Mathematics, vol. 28, pp. 183—186, 1990.

[31] S. Ueno, Y. Kajitani, and H. Wada, “Minimum augmentation of a tree to a k—edge-connected

graph,” NETWORKS, vol. 18, pp. 19-25, 1988.

[32] G. Cai and Y. Sun, “The minimum augmentation of any graph to a k-edge-connected graph,”

NETWORKS, vol. 19. PP. 151—172, 1989.

[33] A. Sengupta, P. D. Joshi, and S. Bandyopadhyay, “A synthesis approach to design optimally
fault tolerant network architecture,” IEEE Transactions on Computers, vol. 40, pp. 94—100,

Jan. 1991.

[34] F. R. K. Chung, “Diameters of graphs: Old problems and new results,” Congressus Numeran-

tium, vol. 60, pp. 295—317, 1987.

[35] R. C. Entringer, D. Jackson, and P. J. Slater, “Geodetic connectivity of graphs,” IEEE Trans-

actions on Circuits and Systems, vol. 24, pp. 460-463, Aug. 1977.

[36] B. Bollabas and S. Eldridge, “On graphs with diameter 2,” Journal of Combinatorial Theory,

Series B, vol. 21, pp. 201—205, 1976.

[37] R. Entringer and D. E. Jackson, “Minimum lc-geodetically connected graphs,” Congressus

Numerantium, vol. 36, pp. 303—309, 1982.

[38] S. Sitarama and A.-H. Esfahanian, “Designing optimal distance-preserving topologies,” De-
partment of Computer Science, Michigan State University, vol. 95, Aug. Technical Report

CPS-94— 1 2.

84

[39] S. Sitarama and A.-H. Esfahanian, “Designing distance-preserving fault-tolerant topologies,”
22nd International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 150—

164, 1996.

[40] S. Sitarama and A.-H. Esfahanian, “Fault-tolerant designs that preserve distance,” Department

of Computer Science, Michigan State University, vol. 96, Oct. Technical Report CPS-96-34.

[41] S. Sitarama and A.-H. Esfahanian, “Distance-preserving graphs,” Journal of Discrete Mathe-

matics, vol. 96, Oct. Submitted for publication.

[42] F. Boesch and R. Tindell, “Connectivity and symmetry in graphs,” Graphs and Applications,

Proceedings of 1 st Colorado Symposium on Graph Theory, pp. 53—67, 1982.

[43] F. Boesch and J. Wang, “Reliable circulant networks with minimum transmission delay,” IEEE

Transactions on Circuits and Systems, vol. 32, pp. 1286—1291, Dec. 1985.
[44] F. Buckley and F. Harary, Distance in Graphs. Addison-Wesley Publishing Company, 1990.
[45] X. Hu and F. Hwang, “Reliabilities of chordal rings,” NETWORKS, vol. 22, pp. 487—501, 1992.

[46] A. Itai, Y. Perl, and Y. Shiloach, “The complexity of finding maximum disjoint paths with

length constraints,” NETWORKS, vol. 12, pp. 277—286, 1982.

[47] M. R. Garey and D. S. Johnson, Computers and Intractability. W. H. Freeman and Company,

1979.

[48] G. Chartrand and L. Lesniak, Graphs and Digraphs. Wadsworth and Brooks/cole mathematics

series, 1979.

"7111111111111111111111“