Minimal dominating sets in graph classes: combinatorial bounds and enumeration

DOI10.1007/978-3-642-27660-6_17MaRDI QIDQ2891369zbMATH OpenOpenAlexFDO

Authors Jean-François Couturier, Pinar Heggernes, Pim Van 't Hof, Dieter Kratsch

Publication date 15 June 2012

Published in SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-27660-6_17

Mathematics Subject Classification ID

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

Recommendations

• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Enumerating minimal dominating sets in chordal graphs
• On the number of minimal dominating sets on some graph classes
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• On maximum number of minimal dominating sets in graphs

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A note on the complexity of the chromatic number problem
• Algorithmic graph theory and perfect graphs
• Combinatorial bounds via measure and conquer
• Enumeration of minimal dominating sets and variants
• Exact exponential algorithms.
• Feedback vertex sets in tournaments
• Finding induced subgraphs via minimal triangulations
• Graph Classes: A Survey
• Node-Deletion Problems on Bipartite Graphs
• On cliques in graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Small Maximal Independent Sets and Faster Exact Graph Coloring
• The domatic number problem on some perfect graph families

Cited in

(19)

• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Bounds on the maximum number of minimum dominating sets
• Minimal dominating sets in interval graphs and trees
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Domination cover number of graphs
• Combinatorial bounds via measure and conquer
• Maximum number of minimum dominating and minimum total dominating sets
• Elimination properties for minimal dominating sets of graphs
• On the enumeration of minimal non-pairwise compatibility graphs
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• scientific article; zbMATH DE number 5131681 (Why is no real title available?)
• Enumerating minimal dominating sets in chordal graphs
• On the number of optimal identifying codes in a twin-free graph
• Algorithms and Computation
• On the number of minimal dominating sets on some graph classes
• Counting minimal dominating sets
• On maximum number of minimal dominating sets in graphs
• scientific article; zbMATH DE number 5953680 (Why is no real title available?)
• On the minimum vertex covering transversal dominating sets in graphs and their classification

This page was built for publication: Minimal dominating sets in graph classes: combinatorial bounds and enumeration

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