Harmonious coloring and labelling of symmetric interconnection networks

Abstract

newline Combinatorial problems have become more important recently newlinein the study of labelling, coverage, connectivity and fault tolerance in newlinecommunication networks. A communication network s topology is often newlinemodeled as an undirected graph and#119866; = (and#119881;, and#119864;) in which the set of vertices and#119881; newlineand the set of edges and#119864; correspond to nodes and links of the network newlinerespectively. There are many optimization problems that associates newlinenetwork with graph theory which are either NP-Complete or NP-Hard. newlineIn this thesis two types of labelling problems are considered: newline1. The Harmonious Chromatic Number Problem (HCNP) newline 2. The Harmonious Labelling Problem (HLP) newline The HCNP in communication networks consists of finding the newlineminimum number of colors that may be interpreted as giving codes to newlinenetwork nodes so that each communication connection can be newlinedifferentiated. newline For a graph and#119866; of size and#119898;, HLP is an assignment and#119891; of distinct newlineelements of the set of integers modulo and#119898; to the vertices of and#119866; so that the newlineresulting edge labelling in which each edge and#119906;and#119907; of and#119866; is labeled and#119891;(and#119906;) + newlineand#119891;(and#119907;) modulo and#119898; is edge-distinguishing. Graphs which admit a newlineharmonious labelling are harmonious graphs. The idea of harmonious