For a graph G = (V, E), a set S ⊆ V is a dominating set if every vertex in V - S is adjacent to at least one vertex in S. A dominating set S ⊆ V is a paired-dominating set if the induced subgraph 〈S〉 has a perfect matching. We introduce a variant of paired-domination where an additional restriction is placed on the induced subgraph 〈S〉. A paired-dominating set S is an induced-paired dominating set if the edges of the matching are the induced edges of 〈S〉, that is, 〈S〉 is a set of independent edges. The minimum cardinality of an induced-paired dominating set of G is the induced-paired domination number γip(G). Every graph without isolates has a paired-dominating set, but not all these graphs have an induced-paired dominating set. We show that the decision problem associated with induced-paired domination is NP-complete even when restricted to bipartite graphs and give bounds on γip(G). A characterization of those triples (a, b, c) of positive integers a ≤ b ≤ c for which a graph has domination number a, paired-domination number b, and induced-paired domination c is given. In addition, we characterize the cycles and trees that have induced-paired dominating sets.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-15784 |
| Date | 01 October 2000 |
| Creators | Studer, Daniel S., Haynes, Teresa W., Lawson, Linda M. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0023 seconds