Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
DOI10.1016/j.dam.2014.09.001zbMath1303.05134arXiv1303.0944OpenAlexW2012547216MaRDI QIDQ477326
Martin Milanič, Nina Chiarelli
Publication date: 3 December 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1303.0944
total dominationforbidden induced subgraph characterizationdually Sperner hypergraphthreshold Boolean functionthreshold hypergraphtotal domishold graph
Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (4)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
- Complexity results for equistable graphs and related classes
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- Independent domination in hereditary classes
- Approximation hardness of dominating set problems in bounded degree graphs
- A survey of selected recent results on total domination in graphs
- Polynomial-time algorithms for regular set-covering and threshold synthesis
- Dominating sets in perfect graphs
- Algorithmic graph theory and perfect graphs
- Threshold graphs and related topics
- On the approximability and exact algorithms for vector domination and related problems in graphs
- Domination and total domination on asteroidal triple-free graphs
- Threshold graphs, shifted complexes, and graphical complexes
- A threshold of ln n for approximating set cover
- On a simple characterisation of threshold graphs
- The structure of threshold graphs
- Linear Separation of Dominating Sets in Graphs
- Equistable graphs
- Total Domination in Graphs
- On the Recognition of k-Equistable Graphs
- On the Enumeration of Minimal Dominating Sets and Related Notions
This page was built for publication: Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs