Monophonic Wirelength in Graph Embedding

Abstract

ABSTRACT newlineA simple graph whose vertices represent the components of the network and edges represent newlineto physical communication links, models an interconnection network. Conversely, any graph newlinecan also be considered as a topological structure of some interconnection network. In newlineinterconnection networks, the simulation of an architecture by another is important. One of newlinethe important features of an interconnection is its ability to simulate programs or parallel newlinealgorithms written efficiently for other architecture. Such a simulation problem can be newlinemathematically formulated as a graph embedding problem. The graph embedding problem newlinein the idea of monophonic can model this problem. newlineThis thesis entitled, quotMonophonic Wirelength in Graph Embeddingquot consists of seven newlinechapters. The basic definitions and the graph theoretic terminologies are discussed in the newlinefirst chapter. The second chapter gives the literature review of the works related to this newlineresearch. By a graph and#1048576; = (V, E), a connected, finite, undirected graph with neither loops newlinenor multiple edges is meant. Consider the graphs G and H of order n. An embedding newlinefm : G and#8594; H is called a monophonic embedding if fm maps each vertex of G into a newlinevertex of H and each edge (x, y) of G is mapped to a monophonic path between fm(x) newlineand fm(y) in H. The monophonic wirelength MWL(G, H) of fm of G into H is given newlineas, MWLfm(G, H) = Í (x,y)and#8712;E(G) newlinedm( fm(x), fm(y)). The monophonic embedding, monophonic newlinewirelength of graph embedding and the distance concepts in graph embedding are framed newlineand the monophonic congestion lemma is proved in the third chapter. newlineClasses of circulant graphs play an important role inmodeling interconnection networks newlinein parallel and distributed computing. The chapters 4, 5 and 6 deal with the monophonic newlineembedding of circulants into various graphs such as grid, wheel, fan and cycle. newlineIn the fourth chapter, an algorithm to find the monophonic wirelength of circulant newlinenetworks into grid is found which leads to find the monophonic wirelength of family of newlinecirculant networks in