Locating-dominating Sets On Paths And Cycles

Let G= (V, E) be a graph and let r≥1 be an integer. Define Nr[x]={y∈V(G): d(x,y)< r｝(where d(x,y) is graph theoretic distance). For a set D c V(G), Dr(x)= Nr[x]∩D. D is known as an r-dominating set, if for all vertices x∈V(G)\D, Dr(x) are all nonempty. When r= 1, D is called a dominating set.Domination problem has many important application to combinatorial optimization, coding theory, computer science, communication networks, monitor system and social net-works. It has been one of the fastest growing areas in graph theory in recent decades. With a detailed study, various new control parameters are emerging. The locating-dominating set is based on its being put forward. The locating-dominating set has been more active research in coding theory, it has wide range of applications in communication networks and monitor system.If the dominating set on the basis of adding some restriction, for all vertices x∈V(G)\D, Dr(x) are all nonempty and different, then, D is a r-locating-dominating set. Denote by MrLD(G) be the smallest possible cardinality of an r-locating-dominating set in G.It is very hard to find a r-locating-dominating set in G, even G is a path or cycle. 2-locating-domination problem of paths and cycles have been solved. In this thesis, we discuss 3-locating-domination problem on paths and cycles. For any r≥2, the paths and cycles have new upper bound about MrLD(G). Moreover, the balloom which consists of one path and one cycle problem is also discussed.