Abstract
dc:descriptionGiven an undirected and simple graph G = (V , E), a subset D of the vertex set is called a k-dominating set if every vertex not in D has at least k neighbors in D. This concept was introduced by Fink and Jacobson in the year 1985, generalizing the already much studied concept of domination in graphs. In particular, we are interested in finding k-dominating sets of minimum cardinality. Inspired by Fink and Jacobson, Cockayne, Gamble and Shepherd proved in the same year that the k- domination of every graph with minimum degree at least k is at most k/(k + 1) times its order. Since then, the concept of k-domination has gained increased popularity among graph theorists. This thesis aims basically to make a contribution to the study of k-domination in graphs. In the first chapter, we introduce the concepts of domination and k- domination. As it was shown in 1989 by Jacobson and Peters, the problem of finding a minimum k-dominating set belongs to the class of NP-hard problems. However, for some graph classes this problem turns polynomial. We present here a polynomial algorithm for finding a minimum f-dominating set in a block graph, where f-domination is an even more general concept as k-domination. This algorithm comprises previous known ones for trees or rather block graphs. The second chapter handles with different bounds on the k-domination number. First, we present an Erdös-type argument that is useful in proving different inequalities. In particular, beside some new bounds on the k-domination number, we derive a classical bound on the k-domination number due to Caro and Roditty and another of Hopkins and Staton on the k-dependence number. Moreover, we are able to characterize the graphs achieving equality in the bound of Cockayne, Gamble and Shepherd mentioned above. Further, we use a probabilistic method in order to obtain other upper bounds for the k-domination number. As a consequence of one of these probabilistic approaches, it follows a well-known inequality for the usual domination number given by Arnautov, Lovasz and Payan. The last part of this chapter is devoted to the analysis of the graphs achieving equality a bound concerning the k-domination and domination parameters, given by Fink and Jacobson. Here, we present different interesting properties of the extremal graphs. In particular, we show that such graphs contain many induced cycles of length four. Moreover, we characterize the claw-free graphs, the line graphs and the cactus graphs with equal 2-domination and domination numbers. In Chapter 3, we compare the k-domination number with other graph parameters. Further, we analyze the connections between the 2-domination number and the independent domination number, which denotes the minimum cardinality of an independent dominating set in G, and we obtain similar results to previous given ones concerning usual domination. Finally, we explore the relations between the k-domination number and the matching number, the connected domination number and the total domination number. The fourth and last chapter is devoted to special k-domination parameters, where, apart from being k-dominating, we demand the k-dominating set to fulfill further properties, like for example that the underlying induced subgraph is connected or that not only the vertices outside the dominating set but also the vertices inside should be k-dominated. Regarding the respective parameters for the minimum number of vertices required for a subset of vertices in a graph to be k-dominating and satisfying a determined property, we develop some interesting bounds that often either generalize or improve known ones.
Degree
thesis:*- Grantor dc:publisher
- Publikationsserver der RWTH Aachen University
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Hansberg Pastor, Adriana
- Contributors dc:contributor
-
- Volkmann, Lutz
Subjects
dc:subject × 7Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- eng