Distance Parameters In Oriented Networks

Abstract

A graph is a mathematical model consisting of vertices and edges. Edges are lines newlinejoining certain pairs of vertices. The diameter diam(G) of a graph G is defined as the newlinemaximum of distances between all pairs of vertices of G. A directed graph or digraph newlineis a graph with a direction assigned to each of its edges. Given any two vertices u and v in a digraph G, if there is a directed path from u to v and a directed path from v to u, then G is said to be strongly connected. To an undirected graph G, if an orientation O is given to its edges, then the resulting digraph is called an oriented graph denoted by G(O). Since there is a choice to assign two orientations to each edge of graph G, there are 2jEj different oriented graphs possible, where E denotes the edge set of graph G. The main motivation for the thesis is the study of Distance parameters in Oriented Graphs . One of the major problems in graph theory is to find the oriented diameter of a graph G, which is defined as the smallest diameter among the diameters of all strongly connected orientations. It shows that the problem is NP-complete (Garey and Johnson, 1979). The oriented grid diameter is obtained in this thesis. Further, we have computed the oriented diameter of the r-level sibling tree ST(r), r _ 2 and the butterfly network. We have also found oriented diameter for triangular networks, slim trees, helms and cactus networks. A duplex graph of G is obtained by introducing a new vertex for every edge of G and joining the new vertex to the end vertices of the corresponding edge. It is denoted by GD. If G is a tree or a cycle or a ladder, then the resulting graph is called a duplex tree or a duplex cycle or a duplex ladder. Wiener (Wiener, 1947) introduced a topological index called Wiener index of an undirected graph G based on distances and defined it as W(G) = 1=2 P newlineu;v2V (G) dG(u; v) where, dG(u; v) is the distance between u and v in G. In computer science, Wiener index is referred to as network distance (soltes, 1986). The oriented Wiener index and#1048576;! W(G)