Zobecněná dominace v degenerovaných grafech: Úplná dichotomie výpočetní složitosti

Abstrakt

Ukazujeme, že pro každé číslo k je otázka existence (sigma,ro)-dominující množiny v daném k=degenerovaném grafu buď polynomiální nebo NP-úplná, a podáváme úplnou charakterizaci těchto případů pro konečné množiny sigma a ro.

Klíčová slova

• Generalized
• domination
• degenerate
• graphs
• complete
• dichotomy
• computational
• complexity