The Minimum Dominating Set problem is polynomial for (claw, P8)-free graphs

Authors:

Preprint

Publisher website

24 September 2021

preprint
Published by arXiv in arXiv

DOI:10.48550/arXiv.2001.07554

Abstract

We prove that the Minimum Dominating Set problem is polynomial for the class of (claw, P8)-free graphs.

Keywords

All Related Versions

This publication has 7 references indexed in Scilit:

A complexity dichotomy and a new boundary class for the dominating set problem
Journal of Combinatorial Optimization, 2015
Fundamentals of Domination in Graphs
2013
Dominating sets for split and bipartite graphs
Information Processing Letters, 1984
Domination alteration sets in graphs
Discrete Mathematics, 1983
Independent domination in chordal graphs
Operations Research Letters, 1982
Edge Dominating Sets in Graphs
SIAM Journal on Applied Mathematics, 1980
A linear algorithm for the domination number of a tree
Information Processing Letters, 1975