Please use this identifier to cite or link to this item: https://doi.org/10.1016/S0012-365X(03)00187-0
DC FieldValue
dc.titleH-domination in graphs
dc.contributor.authorKoh, K.M.
dc.contributor.authorLim, B.B.
dc.contributor.authorSlater, P.J.
dc.date.accessioned2014-10-28T02:36:18Z
dc.date.available2014-10-28T02:36:18Z
dc.date.issued2003-10-28
dc.identifier.citationKoh, 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
dc.identifier.issn0012365X
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/103364
dc.description.abstractLet 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/S0012-365X(03)00187-0
dc.sourceScopus
dc.subjectEfficient domination
dc.subjectH-domination
dc.subjectPaired domination
dc.typeArticle
dc.contributor.departmentMATHEMATICS
dc.description.doi10.1016/S0012-365X(03)00187-0
dc.description.sourcetitleDiscrete Mathematics
dc.description.volume272
dc.description.issue1
dc.description.page97-105
dc.description.codenDSMHA
dc.identifier.isiut000186018400010
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Page view(s)

95
checked on Mar 28, 2020

Google ScholarTM

Check

Altmetric


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