Design of Algorithms to Solve some Labelling Problems on Graphs with Applications

Abstract

In this thesis, graph labelling, particularly L(h; k)-labelling and its variants are discussed. Some problem on fuzzy graphs are also considered here. Colouring on m-polar fuzzy graphs are investigated. Algorithms for some problems are designed and illustrated by examples, the time complexity for each algorithm is also analysed. The thesis is divided into seven chapters. A brief summary of each chapter is given below. In Chapter 1, the introduction of the thesis is given. In this chapter, some de_nitions are given, which are used throughout the thesis. The de_nition of L(2; 1)-labelling, fuzzy sets and graphs, and m-polar fuzzy graphs is provided. This chapter provided a review of the previous works and the motivation of the work. Chapter 2 contains a variant of L(2; 1)-labelling problem. In L(2; 1)-labelling problem, all the vertices are L(2; 1)-labelled by the least number of labels. In this chapter, the maximum allowable label K is given. The problem is de_nedbelow. L(2; 1)-label the vertices of G by using the labels f0; 1; 2; : : : ;Kg such that a maximum number of vertices get a label. If K labels are adequate for labelling all the vertices of the graph, then all vertices get labelled; otherwise, some vertices remain unlabeled. An algorithm is designed to solve this problem. Examples also illustrate the algorithm. Also, an algorithm is designed to test whether an interval graph is no hole label or not for the purpose of L(2; 1)-labelling. In Chapter 3, a variety of L(2; 1)-labelling problem called r-L(2; 1)-labelling problem is consider for circular-arc graph. The L(2; 1)-labelling for a graph G = (V;E), is a function ` from the set of vertices V to the set of non-negative integers with a condition that the vertices which are adjacent assign labels whose di_erence is at least two and the vertices whose distance is two, assign distinct labels. The di_erence between maximum and minimum labels among all possible labels is denoted by _2;1(G). This chapter contains a variant of L(2; 1)-labelling problem. In L(2; 1)-labelling problem, all the vertices are L(2; 1)-labelled by the minimum number of labels. Here, we consider a restricted L(2; 1)-labelling problem, i.e. there is a limitation on the highest label and let it be r. So, in this problem, the valid labels are f0; 1; 2; : : : ; rg. Thus, the problem is: L(2; 1)-label the vertices of G by using the labels f0; 1; 2; : : : ; rg such that a maximum number of vertices gets a label. If r labels are adequate for labelling all the vertices of the graph, then all vertices get labelled; otherwise, some vertices remain unlabeled. A polynomial-time algorithm is designed to solve this problem. The algorithm is illustrated by examples. Also, an application is presented to _nd the appropriate program slots from telecasting channels for advertising the product of a manufacturing company or any other information for any organization. In Chapter 4, interval-valued fuzzy cliques (IVFQs) and interval-valued fuzzy clique covers (IVFQCs) of an interval-valued fuzzy graph (IVFG) are introduced by introducing the fuzziness because, the crisp graphs has some limitations in real world due to uncertainty of vagueness. Here, the concept of cliques and clique covers are slightly modi_ed so that every IVFQ is complete. Also, a clique cover of a crisp graph always covers all the edges and vertices of the graph whereas, the IVFQCs obtained by fuzzify to the clique covers does not satisfy the property. Hence, the de_nition is modi_ed and studied some theorems on it. To better understand the usability of this work, a model application is presented in this chapter. A novel technique is adapted to _nd the eigenvalues and eigenvectors of an intervalvalued fuzzy graph (IVFG) using max-min operators in Chapter 5. The energy of an IVFG is de_ned and computed using max-min operators. Finally, an application of eigenvalues of an IVFG is discussed for the ecological system. In ecology, the amount of food consumed by a predator from the prey is represented as interval-valued fuzzy membership values, which is natural as the food consumption for a predator from prey is uncertain. So this application is very much appropriate for eigenvalues and eigenvectors and energy of an IVFG. Chapter 6 is devoted to the edge colouring of m-polar fuzzy graph (mPFG). The edge colouring for crisp graphs is a well-de_ned topic. But, the edge-colouring for fuzzy graphs has been de_ned recently and investigated many properties. A m-polar fuzzy graph (mPFG) is an extension of a fuzzy graph. The membership values of nodes and edges in mPFG are the vectors with m components. So, some new idea is required to de_ne edge-colouring for an mPFG. In this chapter, we studied edge-colouring for mPFG along with many interesting associated properties. Here, the chromatic index as well as its generalizations, called strong chromatic index, are de_ned and related properties are thoroughly investigated. Here, we also _nd out chromatic numbers as well as a strong chromatic number on some well-known mPFG. Relation between chromatic numbers and the strong chromatics number is established. An algorithm is designed for edge-colouring on mPFG. Lastly, a real-life application based on edgecolouring for mPFG has been discussed to show the usefulness of the proposed method. A conclusion of the work presented in the thesis is made in Chapter 7. The scope of future work are also presented.