The Structure of Dominating Subgraphs

Beschreibung

In this work we investigate total domination, connected domination and paired-domination with respect to the size of the dominating sets and the structure of the subgraphs induced by these sets. We show that for a wide range of common graph classes G it is NP- hard to decide whether a given graph has a connected dominating subgraph, total dominating subgraph respectively, which belongs to G. Furthermore, we prove a similar result for the problem of determining the minimal order of such a restricted dominating subgraph, which holds even for some very special instances. We show that on distance-hereditary graphs some of these problems become tractable, by giving a complete description of the subgraphs induced by (inclusionwise) minimal connected dominating sets of distance-hereditary graphs. We prove that if a distance-hereditary graph does not have a dominating vertex, any two minimal connected dominating sets induce isomorphic subgraphs. Furthermore, we show that if a connected distance- hereditary graph is an induced subgraph of another connected distance- hereditary graph, the same holds for their connected dominating subgraphs. We introduce and study the structural domination problem (as was solved for connected domination by Bacs ́o and Tuza recently) for total domination: We characterize the isolate-free graphs for which any isolate-free induced subgraph has a total dominating subgraph with a prescribed additive hereditary property.
In this work we investigate total domination, connected domination and paired-domination with respect to the size of the dominating sets and the structure of the subgraphs induced by these sets. We show that for a wide range of common graph classes G it is NP- hard to decide whether a given graph has a connected dominating subgraph, total dominating subgraph respectively, which belongs to G. Furthermore, we prove a similar result for the problem of determining the minimal order of such a restricted dominating subgraph, which holds even for some very special instances. We show that on distance-hereditary graphs some of these problems become tractable, by giving a complete description of the subgraphs induced by (inclusionwise) minimal connected dominating sets of distance-hereditary graphs. We prove that if a distance-hereditary graph does not have a dominating vertex, any two minimal connected dominating sets induce isomorphic subgraphs. Furthermore, we show that if a connected distance- hereditary graph is an induced subgraph of another connected distance- hereditary graph, the same holds for their connected dominating subgraphs. We introduce and study the structural domination problem (as was solved for connected domination by Bacs ́o and Tuza recently) for total domination: We characterize the isolate-free graphs for which any isolate-free induced subgraph has a total dominating subgraph with a prescribed additive hereditary property.

Autor*in

Oliver Schaudt

Stimmen zu »The Structure of Dominating Subgraphs«

Details

Link teilen