INVESTIGADORES
TORRES Pablo Daniel
artículos
Título:
{k}-domination for chordal graphs and related graph classes
Autor/es:
G. R. ARGIROFFO; VALERIA LEONI; P. D. TORRES
Revista:
Electronic Notes in Discrete Mathematics
Editorial:
Elsevier
Referencias:
Año: 2013 vol. 44 p. 219 - 224
ISSN:
1571-0653
Resumen:
In this work we obtain a new graph class where the {k}-dominating function problem({k}-DOM) is NP-complete: the class of chordal graphs. We also identify somemaximal subclasses for which it is polynomial time solvable. Firstly, by relatingthis problem with the k-dominating function problem (k-DOM), we prove that{k}-DOM is polynomial time solvable for strongly chordal graphs. Besides, byexpressing the property involved in k-DOM in Counting Monadic Second-orderLogic, we obtain that both problems are linear time solvable for bounded tree-width graphs. Finally, we show that {k}-DOM is linear time solvable for spidergraphs.
