Linear separation of connected dominating sets in graphs
From MaRDI portal
Publication:5225055
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5852793 (Why is no real title available?)
- scientific article; zbMATH DE number 43754 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- scientific article; zbMATH DE number 3385535 (Why is no real title available?)
- scientific article; zbMATH DE number 2209525 (Why is no real title available?)
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- A dominating-set-based routing scheme in ad hoc wireless networks
- A linear time algorithm to list the minimal separators of chordal graphs
- A new polynomial-time algorithm for linear programming
- A note on connected dominating sets of distance-hereditary graphs
- A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic graph theory and perfect graphs
- An O(m n) algorithm for regular set-covering problems
- An O(nm)-time algorithm for computing the dual of a regular Boolean function
- Analytical approach to parallel repetition
- Complexity results for equistable graphs and related classes
- Computational aspects of monotone dualization: a brief survey
- Connected dominating set. Theory and applications
- Connected domination of regular graphs
- Dualization of regular Boolean functions
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Efficient algorithms for the minimum connected domination on trapezoid graphs
- Efficient enumeration of all minimal separators in a graph
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Graph Classes: A Survey
- Hamilton cycles in split graphs with large minimum degree
- Hereditarily dominated graphs
- Hereditary dominating pair graphs
- Linear Separation of Dominating Sets in Graphs
- Linear separation of total dominating sets in graphs
- Listing all Minimal Separators of a Graph
- Minimal vertex separators of chordal graphs
- On connected domination in unit ball graphs
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- On graphs for which the connected domination number is at most the total domination number
- On rigid circuit graphs
- On the enumeration of minimal dominating sets and related notions
- On the recognition of \(k\)-equistable graphs
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- Quasi-threshold graphs
- Rainbow connection number and connected dominating sets
- Solving connected dominating set faster than \(2^n\)
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
- The complexity of domination problems in circle graphs
- Threshold graphs and related topics
- Threshold graphs, shifted complexes, and graphical complexes
- Threshold hypergraphs
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
- Treewidth and minimum fill-in: Grouping the minimal separators
- Trivially perfect graphs
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- Weighted domination of cocomparability graphs
Cited in
(5)
This page was built for publication: Linear separation of connected dominating sets in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5225055)
