Please use this identifier to cite or link to this item: https://doi.org/10.1016/S0012-365X(03)00187-0
Title: H-domination in graphs
Authors: Koh, K.M. 
Lim, B.B.
Slater, P.J.
Keywords: Efficient domination
H-domination
Paired domination
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.

Page view(s)

64
checked on Oct 19, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.