Dominating Colour Transversals in Graphs

Abstract

Domination is a fast developing area in Graph Theory. The concept of domination leads to very interesting research work with good applications. The domination number was defined by Claude Berge in 1958 but only in 1962, Oystein Ore formally defined the domination number of a graph. The survey article published by Cockayne et al., the MRI lecture notes of H.B. Walikar et al., and the two books authored by T.W. Haynes et al., laid a foundation for the growth of Domination Theory. Vizing s conjecture (1963) is still an unsolved problem in Domination Theory. In this research work, three areas of Graph Theory namely Domination, Colouring and Transversal theory are combined judiciously to define a new domination parameter. Let G = (V,E) be a graph. A non-empty set D and#8838; V is called a dominating set of G if every vertex in V and#8722; D is adjacent to Summary of the Thesis 2 some vertex of D. Let C be the collection of all dominating sets of G. The member of C whose cardinality is minimum is called a -set and its cardinality is defined to be the domination number of G and it is denoted by . A partition of the vertex set V into a minimum number of disjoint equivalence classes of independent sets, called colour classes, is said to be a _-partition of G and this minimum number is denoted by _. A dominating set is called a dominating colour transversal set (std-set) if it has a non-empty intersection with every colour class of some _-partition of G. This set is called an std-set because it is transversal of at least one (single) _-partition of G. An std-set with minimum cardinality is called a st-set and its cardinality is denoted by st. Chapter 1This chapter contains basic definitions and results of graph theory and domination theory which are used in the subsequent chaptersHereunder we give a list of important theorems in various chapters in the thesis: newlineSummary of the Thesis 3 Chapter 2 (i) st is determined for various standard graphs including product graphs.