## 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⊆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.

Original language | English |
---|---|

Pages (from-to) | 41-52 |

Number of pages | 12 |

Journal | Discrete Applied Mathematics |

Volume | 259 |

DOIs | |

State | Published - 30 Apr 2019 |

## Keywords

- Cactus graphs
- Domination
- Stability
- Strongly chordal graphs
- Transferability