Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs

DOI10.1016/J.DAM.2014.09.001zbMATH Open1303.05134OpenAlexW2012547216MaRDI QIDQ477326FDOQ477326

Authors: Nina Chiarelli, Martin Milanič 

Publication date: 3 December 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1303.0944

Recommendations

• Linear separation of total dominating sets in graphs
• On a class of graphs between threshold and total domishold graphs
• Polytope Des Absorbants Dans Une Classe De Graphe a Seuil
• Structure and recognition of domishold graphs
• Pseudodomishold graphs

zbMATH Keywords

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

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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 total dominating sets in graphs
• Pseudodomishold graphs
• Title not available (Why is that?)
• Linear separation of connected dominating sets in graphs
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• Total matchings and total coverings of threshold graphs
• Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
• Decomposing 1-Sperner hypergraphs
• Polytope Des Absorbants Dans Une Classe De Graphe a Seuil
• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• On a class of graphs between threshold and total domishold graphs
• Structure and recognition of domishold graphs
• Title not available (Why is that?)

Uses Software

• JBool

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)