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

DOI10.1016/J.DAM.2014.09.001zbMATH Open1303.05134arXiv1303.0944OpenAlexW2012547216MaRDI 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

• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equistable graphs
• Total domination in graphs
• On the recognition of \(k\)-equistable graphs
• Complexity results for equistable graphs and related classes
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• A survey of selected recent results on total domination in graphs
• On the enumeration of minimal dominating sets and related notions
• Dominating sets in perfect graphs
• On the approximability and exact algorithms for vector domination and related problems in graphs
• Domination and total domination on asteroidal triple-free graphs
• Title not available (Why is that?)
• Approximation hardness of dominating set problems in bounded degree graphs
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• Threshold graphs, shifted complexes, and graphical complexes
• On a simple characterisation of threshold graphs
• The structure of threshold graphs
• Title not available (Why is that?)
• Linear Separation of Dominating Sets in Graphs
• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• Independent domination in hereditary classes

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)