Please use this identifier to cite or link to this item:
http://hdl.handle.net/10603/331822
Title: | Distance Parameters In Oriented Networks |
Researcher: | Rajesh, M |
Guide(s): | Indra Rajasingh |
Keywords: | Computer Science Computer Science Hardware and Architecture Engineering and Technology |
University: | VIT University |
Completed Date: | 2020 |
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) |
Pagination: | i,x, 112 |
URI: | http://hdl.handle.net/10603/331822 |
Appears in Departments: | School of Computing Science and Engineering -VIT-Chennai |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
01-title_page.pdf | Attached File | 121.06 kB | Adobe PDF | View/Open |
02-declaration_certificate_signedcopy.pdf | 61.68 kB | Adobe PDF | View/Open | |
03-abstract.pdf | 147.56 kB | Adobe PDF | View/Open | |
04-acknowledgement.pdf | 45.16 kB | Adobe PDF | View/Open | |
05-contents.pdf | 97.55 kB | Adobe PDF | View/Open | |
06-listoffigures.pdf | 138.57 kB | Adobe PDF | View/Open | |
07-listofabbrevations.pdf | 41.42 kB | Adobe PDF | View/Open | |
08-chapter_01.pdf | 384.78 kB | Adobe PDF | View/Open | |
09-chapter_02.pdf | 307.22 kB | Adobe PDF | View/Open | |
10-chapter_03.pdf | 297.68 kB | Adobe PDF | View/Open | |
11-chapter_04.pdf | 486.18 kB | Adobe PDF | View/Open | |
12-chapter_05.pdf | 365.78 kB | Adobe PDF | View/Open | |
13-chapter_06.pdf | 247.29 kB | Adobe PDF | View/Open | |
14-chapter_07.pdf | 236.55 kB | Adobe PDF | View/Open | |
15-chapter_08.pdf | 239.82 kB | Adobe PDF | View/Open | |
17-publications.pdf | 60.19 kB | Adobe PDF | View/Open | |
80_recommendation.pdf | 121.06 kB | Adobe PDF | View/Open |
Items in Shodhganga are licensed under Creative Commons Licence Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0).
Altmetric Badge: