Linear separation of connected dominating sets in graphs
From MaRDI portal
Publication:5225055
DOI10.26493/1855-3974.1330.916zbMATH Open1416.05207arXiv1610.06539OpenAlexW2395657177MaRDI QIDQ5225055FDOQ5225055
Authors: Nina Chiarelli, Martin Milanič 
Publication date: 25 July 2019
Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1610.06539
Recommendations
split graphpolynomial-time algorithmchordal graphconnected dominationforbidden induced subgraph characterizationminimal separatorconnected dominating setthreshold Boolean functionthreshold hypergraphminimal cutset1-Sperner hypergraphconnected-domishold graph
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Hypergraphs (05C65) Structural characterization of families of graphs (05C75)
Cites Work
- Title not available (Why is that?)
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- Rainbow connection number and connected dominating sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the recognition of \(k\)-equistable graphs
- Complexity results for equistable graphs and related classes
- On rigid circuit graphs
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- Trivially perfect graphs
- On the enumeration of minimal dominating sets and related notions
- Algorithmic Aspects of Vertex Elimination on Graphs
- Quasi-threshold graphs
- Efficient enumeration of all minimal separators in a graph
- Treewidth and minimum fill-in: Grouping the minimal separators
- Listing all Minimal Separators of a Graph
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Analytical approach to parallel repetition
- Connected domination of regular graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computational aspects of monotone dualization: a brief survey
- Solving connected dominating set faster than \(2^n\)
- Threshold hypergraphs
- The complexity of domination problems in circle graphs
- Weighted domination of cocomparability graphs
- Efficient algorithms for the minimum connected domination on trapezoid graphs
- A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
- On graphs for which the connected domination number is at most the total domination number
- A note on connected dominating sets of distance-hereditary graphs
- Connected dominating set. Theory and applications
- On connected domination in unit ball graphs
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- Threshold graphs, shifted complexes, and graphical complexes
- Linear Separation of Dominating Sets in Graphs
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
- The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
- Linear separation of total dominating sets in graphs
- A dominating-set-based routing scheme in ad hoc wireless networks
- Dualization of regular Boolean functions
- An \(O(nm)\)-time algorithm for computing the dual of a regular Boolean function
- Hamilton cycles in split graphs with large minimum degree
- Hereditarily dominated graphs
- Minimal vertex separators of chordal graphs
- A linear time algorithm to list the minimal separators of chordal graphs
- An O(m n) algorithm for regular set-covering problems
- Weighted connected domination and Steiner trees in distance-hereditary graphs
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- Hereditary dominating pair graphs
Cited In (5)
Uses Software
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)
