Linear separation of connected dominating sets in graphs

A connected dominating set in a graph is a dominating set of vertices that induces a connected subgraph. In this talk we present graphs in which 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, and we also give several characterizations for the hereditary case, that is, when each connected induced subgraph is required to be connected-domishold.