Mutual transferability for (F, B, R)-domination on strongly chordal graphs and cactus graphs

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.