A characterisation of cycle-disjoint graphs with unique minimum weakly connected dominating set

Abstract

Let G be a connected graph with vertex set V (G). A set S of vertices in G is called a weakly connected dominating set of G if (i) S is a dominating set of G and (ii) the graph obtained from G by removing all edges joining two vertices in V (G) \ S is connected. A weakly connected dominating set S of G is said to be minimum or a γ w-set if {pipe}S{pipe} is minimum among all weakly connected dominating sets of G. We say that G is γ w-unique if it has a unique γ w-set. Recently, a constructive characterisation of γ wunique trees was obtained by Lemanska and Raczek [Czechoslovak Math. J. 59 (134) (2009), 95-100]. A graph is said to be cycle-disjoint if no two cycles in G have a vertex in common. In this paper, we extend the above result on trees by establishing a constructive characterisation of γ w-unique cycle-disjoint graphs.