Abstract | ||
---|---|---|
Let H be some fixed graph of order p. For a given graph G and vertex set S@?V(G), we say that S is H-decomposable if S can be partitioned as S=S\"1@?S\"2@?...@?S\"j where, for each of the disjoint subsets S\"i, with 1=, the subgraph induced by S\"i. We define the H-domination number of G, denoted as @c\"H(G), to be the minimum cardinality of an H-decomposable dominating set S. If no such dominating set exists, we write @c\"H(G)=~. We show that the associated H-domination decision problem is NP-complete for every choice of H. Bounds are shown for @c\"H(G). We show, in particular, that if @d(G)=2, then @c\"P\"\"\"3(G)= |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0012-365X(03)00187-0 | Discrete Mathematics |
Keywords | Field | DocType |
h -domination,paired domination,efficient domination,h-domination,dominating set,domination number,decision problem | Graph theory,Graph,Discrete mathematics,Dominating set,Decision problem,Combinatorics,Disjoint sets,Vertex (geometry),Subgroup,Cardinality,Mathematics | Journal |
Volume | Issue | ISSN |
272 | 1 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
K. M. KOH | 1 | 352 | 53.07 |
Bock Boom Lim | 2 | 0 | 0.34 |
Peter J. Slater | 3 | 593 | 132.02 |