Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs
Simple item page Statistics| Field | Value | Language |
|---|---|---|
dc.citation.epage |
52 | en_US |
dc.citation.spage |
41 | en_US |
dc.citation.volume |
259 | en_US |
dc.citation.woscount |
0 | en_US |
dc.contributor.author |
Chu, Kuan-Ting | en_US |
dc.contributor.author |
Lin, Wu-Hsiung | en_US |
dc.contributor.author |
Chen, Chiuyuan | en_US |
dc.contributor.department |
應用數學系 | zh_TW |
dc.contributor.department |
Department of Applied Mathematics | en_US |
dc.date.accessioned |
2019-06-03T01:08:33Z | |
dc.date.available |
2019-06-03T01:08:33Z | |
dc.date.issued |
2019-04-30 | en_US |
dc.description.abstract |
This paper studies a variation of domination in graphs called (F, B, R)-domination. Let G = (V, E) be a graph and V be the disjoint union of F, B, and R, where F consists of free vertices, B consists of bound vertices, and R consists of required vertices. An (F, B, R)-dominating set of G is a subset D subset of V such that R subset of D and each vertex in B - D is adjacent to some vertex in D. An (F, B, R)-2-stable set of G is a subset S subset of B such that S boolean AND N(R) = empty set and every two distinct vertices x and y in S have distance d(x, y) > 2. We prove that if G is strongly chordal, then alpha(F,B,R,2) (G) = gamma(F,B,R)(G)-vertical bar R vertical bar, where gamma(F,B,R)(G) is the minimum cardinality of an (F, B, R)-dominating set of G and alpha(F,B,R,2) (G) is the maximum cardinality of an (F, B, R)-2-stable set of G. Let D-1 ->* D-2 denote D1 being transferable to D-2. We prove that if G is a connected strongly chordal graph in which D-1 and D-2 are two (F, B, R)-dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 ->* D-2. We also prove that if G is a cactus graph in which D-1 and D-2 are two (F, B, R) -dominating sets with vertical bar D-1 vertical bar = vertical bar D-2 vertical bar, then D-1 boolean OR {1.extra} ->* D-2 boolean OR{1.extra}, where boolean OR{1.extra} means adding one extra element. (C) 2019 Elsevier B.V. All rights reserved. | en_US |
dc.identifier.doi |
10.1016/j.dam.2018.12,034 | en_US |
dc.identifier.issn |
0166-218X | en_US |
dc.identifier.journal |
DISCRETE APPLIED MATHEMATICS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.dam.2018.12,034 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/151927 | |
dc.identifier.wosnumber |
WOS:000466061100004 | en_US |
dc.language.iso |
en_US | en_US |
dc.subject |
Domination | en_US |
dc.subject |
Stability | en_US |
dc.subject |
Transferability | en_US |
dc.subject |
Strongly chordal graphs | en_US |
dc.subject |
Cactus graphs | en_US |
dc.title |
Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs | en_US |
dc.type |
Article | en_US |
Files
No files are attached to this item.
Collections: Articles
Cite this item
Chu, K.-T., Lin, W.-H., & Chen, C. (2019). Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs. DISCRETE APPLIED MATHEMATICS, 259, 41–52. https://doi.org/10.1016/j.dam.2018.12,034
Citation generated in APA 7th edition style; please check it before use.
Share
Permanent link: https://ir.lib.nycu.edu.tw/handle/11536/151927