PT Unknown
AU Löwenstein Dr.rer.nat., C
TI In the complement of a dominating set
PD August
PY 2010
WP https://www.db-thueringen.de/receive/dbt_mods_00016280
LA en
DE domination; disjoint domination; total domination; independence; spanning tree congestion
AB A set D of vertices of a graph G=(V,E) is a dominating set, if every vertexof D\V has at least one neighbor that belongs to D. The disjoint dominationnumber of a graph G is the minimum cardinality of two disjoint dominatingsets of G. We prove upper bounds for the disjoint domination number forgraphs of minimum degree at least 2, for graphs of large minimum degree andfor cubic graphs.A set T of vertices of a graph G=(V,E) is a totaldominating set, if every vertex of G has at least one neighbor that belongsto T. We characterize graphs of minimum degree 2 without induced 5-cyclesand graphs of minimum degree at least 3 that have a dominating set, a totaldominating set, and a non-empty vertex set that are disjoint.A set I ofvertices of a graph G=(V,E) is an independent set, if all vertices in I arenot adjacent in G. We give a constructive characterization of trees thathave a maximum independent set and a minimum dominating set that aredisjoint and we show that the corresponding decision problem is NP-hard forgeneral graphs. Additionally, we prove several structural and hardnessresults concerning pairs of disjoint sets in graphs which are dominating,independent, or both. Furthermore, we prove lower bounds for the maximumcardinality of an independent set of graphs with specifed odd girth andsmall average degree.A connected graph G has spanning tree congestion atmost s, if G has a spanning tree T such that for every edge e of T the edgecut defined in G by the vertex sets of the two components of T-e containsat most s edges. We prove that every connected graph of order n hasspanning tree congestion at most n^(3/2) and we show that the correspondingdecision problem is NP-hard.
ER