TY - JOUR
T1 - Mutual transferability for (F,B,R)-domination on strongly chordal graphs and cactus graphs
AU - Chu, Kuan Ting
AU - Lin, Wu-Hsiung
AU - Chen, Chiuyuan
N1 - Publisher Copyright:
© 2019 Elsevier B.V.
PY - 2019/4/30
Y1 - 2019/4/30
N2 - 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⊆V such that R⊆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⊆B such that S∩N(R)=0̸ 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 α F,B,R,2 (G)=γ F,B,R (G)−|R|, where γ F,B,R (G) is the minimum cardinality of an (F,B,R)-dominating set of G and α 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 D 1 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 |D 1 |=|D 2 |, 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 |D 1 |=|D 2 |, then D 1 ∪{1⋅extra}→∗D 2 ∪{1⋅extra}, where ∪{1⋅extra} means adding one extra element.
AB - 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⊆V such that R⊆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⊆B such that S∩N(R)=0̸ 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 α F,B,R,2 (G)=γ F,B,R (G)−|R|, where γ F,B,R (G) is the minimum cardinality of an (F,B,R)-dominating set of G and α 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 D 1 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 |D 1 |=|D 2 |, 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 |D 1 |=|D 2 |, then D 1 ∪{1⋅extra}→∗D 2 ∪{1⋅extra}, where ∪{1⋅extra} means adding one extra element.
KW - Cactus graphs
KW - Domination
KW - Stability
KW - Strongly chordal graphs
KW - Transferability
UR - http://www.scopus.com/inward/record.url?scp=85060235513&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2018.12.034
DO - 10.1016/j.dam.2018.12.034
M3 - Article
AN - SCOPUS:85060235513
SN - 0166-218X
VL - 259
SP - 41
EP - 52
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -