On the number of minimal dominating sets on some graph classes

DOI10.1016/J.TCS.2014.11.006MaRDI QIDQ476916zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in interval graphs and trees
• On maximum number of minimal dominating sets in graphs
• Enumeration and maximum number of minimal dominating sets for chordal graphs

Cites work

• Algorithmic graph theory and perfect graphs
• Combinatorial bounds via measure and conquer
• Enumerating minimal subset feedback vertex sets
• Enumeration of minimal dominating sets and variants
• Exact exponential algorithms.
• Finding induced subgraphs via minimal triangulations
• Graph Classes: A Survey
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On cliques in graphs
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
• On the number of minimal transversals in 3-uniform hypergraphs
• Trees having many minimal dominating sets

Cited in

(24)

• Locally definable vertex set properties are efficiently enumerable
• Enumeration of minimal tropical connected sets
• Combinatorial properties of Farey graphs
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Domination cover number of graphs
• Enumeration of maximal irredundant sets for claw-free graphs
• COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB
• Minimal Roman dominating functions: extensions and enumeration
• Enumeration of maximal irredundant sets for claw-free graphs
• Enumerating minimal dominating sets in chordal graphs
• Enumeration and maximum number of maximal irredundant sets for chordal graphs
• On maximum number of minimal dominating sets in graphs
• Enumerating Minimal Tropical Connected Sets
• 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 dominating sets in interval graphs and trees
• Enumeration and maximum number of minimal dominating sets for chordal graphs
• Maximum number of minimum dominating and minimum total dominating sets
• On the minimum vertex covering transversal dominating sets in graphs and their classification
• Minimal Roman dominating functions: extensions and enumeration
• Dominating Set Counting in Graph Classes

This page was built for publication: On the number of minimal dominating sets on some graph classes

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