info:eu-repo/semantics/article
{k}-domination for chordal graphs and related graph classes
Registro en:
Argiroffo, Gabriela Rut; Leoni, Valeria Alejandra; Torres, Pablo Daniel; {k}-domination for chordal graphs and related graph classes; Elsevier; Electronic Notes in Discrete Mathematics; 44; 11-2013; 219-224
1571-0653
CONICET Digital
CONICET
Autor
Argiroffo, Gabriela Rut
Leoni, Valeria Alejandra
Torres, Pablo Daniel
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 some maximal subclasses for which it is polynomial time solvable. Firstly, by relating this problem with the k-dominating function problem (k-DOM), we prove that {. k}-DOM is polynomial time solvable for strongly chordal graphs. Besides, by expressing the property involved in k-DOM in Counting Monadic Second-order Logic, 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 spider graphs. Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina Fil: Torres, Pablo Daniel. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina