Multiple domination in graphs

Hansberg Pastor, Adriana; Volkmann, Lutz

doi:urn:nbn:de:hbz:82-opus-29122

Multiple domination in graphs = Mehrfache Dominanz in Graphen

Hansberg Pastor, Adriana (Author)

2009

Verantwortlichkeitsangabevorgelegt von Adriana Hansberg Pastor

ImpressumAachen : Publikationsserver der RWTH Aachen University 2009

UmfangXIV, 116 S.

Aachen, Techn. Hochsch., Diss., 2009

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Volkmann, Lutz (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2009-08-17

Online
URN: urn:nbn:de:hbz:82-opus-29122
URL: https://publications.rwth-aachen.de/record/51218/files/Hansberg_Pastor_Adriana.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Graphentheorie (Genormte SW) ; Mathematik (frei) ; k-Dominanz (frei) ; Dominanz (frei) ; k-domination (frei) ; domination (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 05C69

Kurzfassung
Hat man einen nicht gerichteten Graphen G = (V , E) gegeben, dann nennt man eine Teilmenge D der Eckenmenge von G eine k-Dominanzmenge, wenn jede Ecke nicht in D mindestens k Nachbarn in D hat. Dieses Konzept wurde in 1985 von Fink and Jacobson eingeführt, womit der sehr erforschte Begriff von Dominanz in Graphen verallgemeinert wurde, wo k = 1 ist. Insbesondere sind wir daran interessiert, k-Dominanzmengen minimaler Kardinalität zu finden. Angeregt von Fink und Jacobson, Cockayne, Gamble und Shepherd zeigten im gleichem Jahr, dass die Dominanzzahl eines Graphen der Ordnung n und mit Minimalgrad mindestens k maximal k/(k + 1)n Ecken hat. Seitdem hat das Konzept der k-Dominanz immer mehr Popularität zwischen den Graphentheoretikern gewonnen. Diese Disertation erstrebt hauptsächlich, einen Beitrag zum Gebiet der k-Dominanz in Graphen zu leisten. Im ersten Kapitel führen wir die Begriffe der Dominanz und k-Dominanz ein. Wie in 1989 von Jacobson und Peters gezeigt, das Problem, eine minimale Dominanzmenge zu finden, ist ein NP-hartes Optimierungsproblem. Dennoch wird dieses Problem bei bestimmten Graphenklassen polynomial. Wir stellen hier einen polynomiellen Algorithmus vor, mit dem man eine minimale f-Dominanzmenge in einem Blockgraphen findet, wobei f-Dominanz ein weiter allgemeineres Konzept ist als dasjenige von k-Dominanz. Dieses Algorothmus umfasst andere schon gekannte Algorithmen für Bäume bzw. Blockgraphen. Das zweite Kapitel befasst sich mit verschiedenen Schranken für die k-Dominanzzahl. Als erstes stellen wir ein Erdös-artiges Argument vor, das sehr nützlich beim Beweisen von verschiedenen Ungleichungen sein wird. Insbesondere, neben einigen neuen Schranken der k-Dominanzzahl, leiten wir eine klassische Schranke von Caro und Roditty und eine weitere von Hopkins und Staton für die k-Abhängigkeitszahl her. Darüber hinaus gelingt es uns die Charakterisierung der Graphen anzugeben, die die oben erwähnte Schranke von Cockayne, Gamble und Shepherd mit Gleichheit genügen. Weiterhin benutzen wir eine probabilistische Methode, um obere Schranken für die k-Dominanzzahl zu erhalten. Als Folgerung dieses probabilistischen Herangehens, erhalten wir eine wohl bekannte Ungleichung für die übliche Dominanzzahl, gezeigt unabhängigerweise von Arnautov, Lovasz und Payan. Der letzte Teil dieses Kapitels wird an die Analysis der extremalen Graphen bezüglich einer Ungleichung von Fink und Jacobson gewidmet, die die k-Dominanzzahl und die Dominanzzahl miteinbezieht. Wir stellen hier verschiedene interessante Eigenschaften dieser Graphen vor. Insbesondere zeigen wir, dass solche Graphen sehr viele induzierte Kreise der Länge vier besitzen. Zudem charakterisieren wir alle klauenfreien Graphen, Line-Graphen und Kaktusgraphenmit gleichen 2-Dominanz- und Dominanzzahl. Im Kapitel 3 vergleichen wir die k-Dominanzzahl mit anderen Parametern von Graphen. Witerhin erforschen wir die Zusammenhänge zwischen der 2-Dominanzzahl und der unabhängigen Dominanzzahl, welche die Ordnung einer minimalen unabhängigen Dominanzzahl bezeichnet, und erhalten ähnliche Resultate zu manchen vorher gekannten Ergebnissen bezüglich den üblichen Dominanzparameter. Zum Schluss erkunden wir die Zusammenhänge zwischen der k-Dominanzzahl und der Matching-, der zusammenhängenden Dominanz- und der totalen Dominanzzahl. Der vierte und letzte Kapitel ist speziellen k-Dominanzparametern gewidmet, wo außer der k-dominierenden Eigenschaft, noch zusätzliche Forderungen an einer k-Dominanzmenge D gestellt werden, wie zum Beispiel, dass der von D induzierte Teilgraph zusammenhängend ist, oder dass nicht nur die Ecken außerhalb D sondern auch die Ecken in D k-dominiert werden sollen. Wir betrachten die verschiedenen Parametern, die die minimale Ordnung solcher Mengen darstellen, und leiten einige interessante Schranken her, die oft auch manche bekannten Ungleichungen verallgemeinern oder verbessern.

Given 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.

Fulltext:
PDF