Title: A threshold approach to connected domination.
Abstract: A connected dominating set in a graph is a dominating set of vertices that induces a connected subgraph. We introduce and study the connected-domishold graphs, defined as graphs that admit non-negative real weights associated to their 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.
More specifically, we show that connected-domishold graphs form a non-hereditary class of graphs properly containing two well known classes of chordal graphs: the block graphs and the trivially perfect graphs. We characterize connected-domishold graphs in terms of thresholdness of their minimal separator hypergraphs and show, conversely, that connected-domishold split graphs can be used to characterize threshold hypergraphs. Graphs every connected induced subgraph of which is connected-domishold are characterized in terms of forbidden induced subgraphs and in terms of properties of the minimal separator hypergraph. As a side result, our approach leads to new polynomially solvable cases of the minimum-weight connected domination problem.
Publication Year: 2016
Publication Date: 2016-10-20
Language: en
Type: preprint
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot