Please use this identifier to cite or link to this item:
|Title:||H-domination in graphs||Authors:||Koh, K.M.
|Issue Date:||28-Oct-2003||Citation:||Koh, K.M., Lim, B.B., Slater, P.J. (2003-10-28). H-domination in graphs. Discrete Mathematics 272 (1) : 97-105. ScholarBank@NUS Repository. https://doi.org/10.1016/S0012-365X(03)00187-0||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 = S1 ∪ S2 ∪ ⋯ ∪ Sj where, for each of the disjoint subsets Si, with 1 ≤ i ≤ j, we have |Si| = p and H is a spanning subgraph of 〈Si〉, the subgraph induced by Si. We define the H-domination number of G, denoted as γH(G), to be the minimum cardinality of an H-decomposable dominating set S. If no such dominating set exists, we write γH(G) = ∞. We show that the associated H-domination decision problem is NP-complete for every choice of H. Bounds are shown for γH(G). We show, in particular, that if δ(G) ≥ 2, then γP3(G) ≤ 3γ(G). Also, if γP3(G) = 3γ(G), then every γ(G)-set is an efficient dominating set. © 2003 Published by Elsevier B.V.||Source Title:||Discrete Mathematics||URI:||http://scholarbank.nus.edu.sg/handle/10635/103364||ISSN:||0012365X||DOI:||10.1016/S0012-365X(03)00187-0|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jul 20, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.