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

zbMATH Keywords

total dominationforbidden induced subgraph characterizationdually Sperner hypergraphthreshold Boolean functionthreshold hypergraphtotal domishold graph

Mathematics Subject Classification ID

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)

Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs ⋮ On a class of graphs between threshold and total domishold graphs ⋮ Linear separation of connected dominating sets in graphs ⋮ Decomposing 1-Sperner hypergraphs

Uses Software

• JBool

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