On a class of graphs between threshold and total domishold graphs

DOI10.1016/j.dam.2014.02.013zbMath1320.05087OpenAlexW1982529066MaRDI QIDQ496435

Martin Milanič, Nina Chiarelli

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

threshold graphtotal dominationforbidden 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)

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On graphs for which the connected domination number is at most the total domination number
• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• On the existence of total dominating subgraphs with a prescribed additive hereditary property
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• Independent domination in hereditary classes
• A survey of selected recent results on total domination in graphs
• Algorithmic graph theory and perfect graphs
• Threshold graphs and related topics
• Total domination and the Caccetta-Häggkvist conjecture
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• Open packing, total domination, and the \(P_3\)-Radon number
• Incidence matrices and interval graphs
• Two short proofs on total domination
• Linear Separation of Total Dominating Sets in Graphs
• Total domination in graphs
• Linear Separation of Dominating Sets in Graphs
• Equistable graphs
• Total Domination in Graphs

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