On a class of graphs between threshold and total domishold graphs

DOI10.1016/J.DAM.2014.02.013MaRDI QIDQ496435zbMATH OpenOpenAlexFDO

Authors Nina Chiarelli, Martin Milanič

Publication date 21 September 2015

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

Full work available at URL https://doi.org/10.1016/j.dam.2014.02.013

zbMATH Keywords

total dominationthreshold graphforbidden induced subgraph characterizationlinear-time algorithmtotal domishold graphleaf extension of a threshold graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• Linear separation of total dominating sets in graphs
• Pseudodomishold graphs
• Structure and recognition of domishold graphs
• A class of threshold and domishold graphs: Equistable and equidominating graphs

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 6096635 (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
• Algorithmic graph theory and perfect graphs
• Equistable graphs
• Incidence matrices and interval graphs
• Independent domination in hereditary classes
• Linear Separation of Dominating Sets in Graphs
• Linear separation of total dominating sets in graphs
• Nordhaus-Gaddum type results for total domination
• On graphs for which the connected domination number is at most the total domination number
• On the existence of total dominating subgraphs with a prescribed additive hereditary property
• Open packing, total domination, and the P₃-Radon number
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• Threshold graphs and related topics
• Total domination and the Caccetta-Häggkvist conjecture
• Total domination in graphs
• Total domination in graphs
• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• Two short proofs on total domination

Cited in

(9)

• Linear separation of total dominating sets in graphs
• scientific article; zbMATH DE number 4127265 (Why is no real title available?)
• Linear separation of connected dominating sets in graphs
• Enumerating threshold graphs and some related graph classes
• Graphs obtained by disjoint unions and joins of cliques and stable sets
• scientific article; zbMATH DE number 4154497 (Why is no real title available?)
• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• On the pairwise compatibility property of some superclasses of threshold graphs
• Structure and recognition of domishold graphs

Describes a project that uses

Uses Software

• JBool

This page was built for publication: On a class of graphs between threshold and total domishold graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496435)