Please use this identifier to cite or link to this item:
Title: H-domination in graphs
Authors: Koh, K.M. 
Lim, B.B.
Slater, P.J.
Keywords: Efficient 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.
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
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)

checked on Jan 17, 2021

Google ScholarTM



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