A Study on Graph Labelings and Graph Spectra

Abstract

The thesis mainly involves the study of graph labelings and graph spectra with a focus on their applications. Labeled graphs provide a compact representation in which each element of an n-element set S (the signature of the graph) is assigned to a vertex of a graph with n vertices. Edges between vertices only exist when the sum or difference of their respective vertex numbers is one of the elements of the signature. A graph defined by such a signature is a sum graph or difference graph accordingly, and the labeling is called sum or difference labeling. A graph G(V, E) is referred to as a sum graph if there is an injective labeling known as sum labeling f from V (G) to a set of distinct positive integers S such that ab ∈ E(G) if and only if there is a vertex w in V (G) such that f (w) = f (a)+ f (b) ∈ S. Here w is called a working vertex. A sum labeling f is called an exclusive sum labeling with respect to a subgraph H of G, if f is a sum labeling of G, where H contains no working vertex. In this thesis, we obtain the exclusive sum number of several graphs. A possible application of the exclusive sum labeled complete k-partite graph in a relational database is given in this thesis. An autograph(difference graphs) with a signature whose elements are positive integers and contains no repeated elements is called a proper monograph. This thesis investigates the proper monograph labelings of several graphs and obtains their maximum independence number from their signatures. Graphs serve as models for multiprocessor interconnection networks. A link exists between the graph spectra and the design of multiprocessor interconnection networks from the literature. The graphs are termed as well-suited if the value of m∆ is small. Here m is the number of dis- tinct eigenvalues and ∆ is the maximum vertex degree. This thesis defines two new graph tightness values, t3(G) and t4(G), based on the literature’s four types of graph tightness values. Further, we present several well-suited graphs for the design of the multiprocessor intercon- nection networks. Load balancing attempts to improve the performance of a distributed system by transferring some of the workloads of a congested node to other nodes for processing. This thesis studies the dynamic load balancing approach and presents a modified algorithm for load balancing in integer arithmetic. The proposed algorithm generates a balancing flow with a minimum l2 norm.