  A connected dominating set in a graph is a dominating set of vertices that
induces a connected subgraph. Following analogous studies in the literature
related to independent sets, dominating sets, and total dominating sets, we
study in this paper the class of graphs in which the connected dominating sets
can be separated from the other vertex subsets by a linear weight function.
More precisely, we say that a graph is connected-domishold if it admits
non-negative real weights associated to its vertices such that a set of
vertices is a connected dominating set if and only if the sum of the
corresponding weights exceeds a certain threshold. We characterize the graphs
in this non-hereditary class in terms of a property of the set of minimal
cutsets of the graph. We give several characterizations for the hereditary
case, that is, when each connected induced subgraph is required to be
connected-domishold. The characterization by forbidden induced subgraphs
implies that the class properly generalizes two well known classes of chordal
graphs, the block graphs and the trivially perfect graphs. Finally, we study
certain algorithmic aspects of connected-domishold graphs. Building on
connections with minimal cutsets and properties of the derived hypergraphs and
Boolean functions, we show that our approach leads to new polynomially solvable
cases of the weighted connected dominating set problem.
