Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
From MaRDI portal
Publication:477326
Abstract: A total dominating set in a graph is a set of vertices such that every vertex of the graph has a neighbor in the set. We introduce and study graphs that admit non-negative real weights associated to their vertices such that a set of vertices is a total dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We show that these graphs, which we call total domishold graphs, form a non-hereditary class of graphs properly containing the classes of threshold graphs and the complements of domishold graphs, and are closely related to threshold Boolean functions and threshold hypergraphs. We present a polynomial time recognition algorithm of total domishold graphs, and characterize graphs in which the above property holds in a hereditary sense. Our characterization is obtained by studying a new family of hypergraphs, defined similarly as the Sperner hypergraphs, which may be of independent interest.
Recommendations
Cites work
- scientific article; zbMATH DE number 5852793 (Why is no real title available?)
- scientific article; zbMATH DE number 3487492 (Why is no real title available?)
- scientific article; zbMATH DE number 3561379 (Why is no real title available?)
- scientific article; zbMATH DE number 3598234 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (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?)
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- A survey of selected recent results on total domination in graphs
- A threshold of ln n for approximating set cover
- Algorithmic graph theory and perfect graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- Complexity results for equistable graphs and related classes
- Dominating sets in perfect graphs
- Domination and total domination on asteroidal triple-free graphs
- Equistable graphs
- Independent domination in hereditary classes
- Linear Separation of Dominating Sets in Graphs
- On a simple characterisation of threshold graphs
- On the approximability and exact algorithms for vector domination and related problems in 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
- The structure of threshold graphs
- Threshold graphs and related topics
- Threshold graphs, shifted complexes, and graphical complexes
- Total domination in graphs
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
Cited in
(13)- Linear separation of connected dominating sets in graphs
- On a class of graphs between threshold and total domishold graphs
- Total matchings and total coverings of threshold graphs
- Pseudodomishold graphs
- scientific article; zbMATH DE number 4127265 (Why is no real title available?)
- scientific article; zbMATH DE number 6707348 (Why is no real title available?)
- Structure and recognition of domishold graphs
- Decomposing 1-Sperner hypergraphs
- Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
- Linear separation of total dominating sets in graphs
- A class of threshold and domishold graphs: Equistable and equidominating graphs
- Polytope Des Absorbants Dans Une Classe De Graphe a Seuil
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
This page was built for publication: Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477326)
