Skip to Main content Skip to Navigation
Journal articles

On the vertices belonging to all, some, none minimum dominating set

Valentin Bouquet 1, 2 François Delbot 3 Christophe Picouleau 1
1 CEDRIC - OC - CEDRIC. Optimisation Combinatoire
CEDRIC - Centre d'études et de recherche en informatique et communications
2 CEDRIC - ROC - CEDRIC. Réseaux et Objets Connectés
CEDRIC - Centre d'études et de recherche en informatique et communications
Abstract : We characterize the vertices belonging to all minimum dominating sets, to some minimum dominating sets but not all, and to no minimum dominating set. We refine this characterization for some well studied sub-classes of graphs: chordal, claw-free, triangle-free. Also we exhibit some graphs answering to some open questions of the literature on minimum dominating sets.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02434684
Contributor : Christophe Picouleau <>
Submitted on : Friday, January 17, 2020 - 12:30:55 PM
Last modification on : Wednesday, September 2, 2020 - 9:49:04 AM

File

1909.02843.pdf
Files produced by the author(s)

Identifiers

Citation

Valentin Bouquet, François Delbot, Christophe Picouleau. On the vertices belonging to all, some, none minimum dominating set. Discrete Applied Mathematics, Elsevier, 2021, 288, pp.9-19. ⟨10.1016/j.dam.2020.08.020⟩. ⟨hal-02434684⟩

Share

Metrics

Record views

231

Files downloads

56