On the number of minimal dominating sets on some graph classes

DOI10.1016/j.tcs.2014.11.006zbMath1305.05219OpenAlexW1977860733MaRDI QIDQ476916

Romain Letourneur, Mathieu Liedloff, Jean-François Couturier

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.11.006

zbMATH Keywords

graph algorithmsdominating setsgraph classesexponential-time algorithmsenumerating algorithms

Mathematics Subject Classification ID

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

Related Items

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Minimal dominating sets in interval graphs and trees ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Enumeration of minimal tropical connected sets ⋮ COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB ⋮ Enumerating Minimal Tropical Connected Sets ⋮ Domination cover number of graphs ⋮ Locally definable vertex set properties are efficiently enumerable ⋮ Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ Enumerating minimal dominating sets in chordal graphs ⋮ Enumeration and maximum number of minimal dominating sets for chordal graphs ⋮ Combinatorial properties of Farey graphs

Cites Work

• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Exact exponential algorithms.
• On the number of minimal transversals in 3-uniform hypergraphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Algorithmic graph theory and perfect graphs
• Trees having many minimal dominating sets
• On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
• Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration
• Enumeration of Minimal Dominating Sets and Variants
• Finding Induced Subgraphs via Minimal Triangulations
• Graph Classes: A Survey
• On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
• Combinatorial bounds via measure and conquer
• Enumerating Minimal Subset Feedback Vertex Sets
• On cliques in graphs