Studies in graph theory with special reference to degree equal domination and star domination

Abstract

Graph theory is an outcome of Euler s idea in Solving the Konigsberg newlinebridge Problem. Euler in 1736, suggested a new structure called graph for newlinesolving combinatorial problems. A graph consists of a vertex set and an edge set newlinewhere each edge is an unordered pair of vertices. Over the years, many areas in newlinegraph theory were developed for solving problems in social, combinatorial and newlinecommunication network. Due to fast development in computers, many topics in newlinegraph theory were explored with ease. One of these topics is domination. Henda newlineC. Swart has rightly commented that the theory of domination in graphs is like newlinea growth industry . The topic of domination was given formal Mathematical newlinedefinition by Berge in 1958 and Ore in 1962. Berge called the domination newlineas external stability and domination number as coefficient of external stability. newlineOre introduced the word domination in his famous book Theory of Graphs , newlinepublished in 1962. This concept lived almost in hibernation until 1975 when newlineE. J. Cockayne and S.T.Hedetniemi published their paper, Towards a theory newlineof Domination in Graphs which appeared in Networks in 1977. Towards newlinethe end of 1997, T.W. Haynes, S.T.Hedetniemi and P.J.Slater brought out a newlinecomprehensive two volume text book Fundamental of Domination in Graphs newlineand Domination in Graphs: Advanced Topics which contain more than 1200 newlinebibliographical entries. There are many variations of domination in graphs. newlineIn the book by T.W.haynes et al, it is proposed that a type of domination newlineis fundamental if every connected nontrivial graph has a dominating set newlineof this type. Manotypes of domination have been introduced and Studied. newlineSome of them depend upon the nature of domination while other depend on newlinethe type of dominating sets. newline