Search

Let G be a connected graph, and let D (G) be the set of all dominating (multi)sets for G. For D 1 and D 2 in D (G) , we say that D 1 is single-step transferable to D 2 if there exist u ∈ D 1 and v ∈ D 2 , such that u v ∈ E (G) and D 1 − { u } = D 2 − { v }. We write D 1 ⟶ ∗ D 2 if D 1 can be transferred to D 2 through a sequence of single-step transfers. We say that G is k -transferable if D 1 ⟶ ∗ D 2 for any D 1 , D 2 ∈ D (G) with | D 1 | = | D 2 | = k. The transferable domination number of G is the smallest integer k to guarantee that G is l -transferable for all l ≥ k. We study the transferable domination number of graphs in this paper. We give upper bounds for the transferable domination number of general graphs and bipartite graphs, and give a lower bound for the transferable domination number of grids. We also determine the transferable domination number of P m × P n for the cases that m = 2 , 3 , or m n ≡ 0 (mod 6). Besides these, we give an example to show that the gap between the transferable domination number of a graph G and the smallest number k so that G is k -transferable can be arbitrarily large. [ABSTRACT FROM AUTHOR]