1-movable connected dominating sets in graphs
Jocecar Lomarda, Sergio R. Canoy · Applied Mathematical Sciences · 2015
distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. A connected dominating set C in a connected nontrivial graph G is a 1-movable connected dominating set in G if for every v ∈ C, either C \\ {v} is a connected dominating set, or there exists a vertex u ∈ (V (G) \\ C) ∩ N(v) such that (C \\ {v}) ∪ {u} is a connected dominating set of G. The minimum cardinality of a 1-movable connected dominating set of G, denoted by γ1mc (G) is the 1-movable connected domination number of G. A 1-movable connected dominating set with cardinality γ1mc (G) is called a minimum 1-movable connected dominating set or a γ1mc-set of G. In this paper, we characterize those graphs G having a 1-movable connected dominating set. We also characterize the 1-movable connected dominating sets in the join of graphs and determine the corresponding 1-movable connected domination number of these graphs.