Cohabitation of independent sets and dominating sets in trees

Authors

  • Löwenstein, Christian
  • Rautenbach, Dieter

Abstract

We give a constructive characterization of trees that have a maximum independent set and a minimum dominating set which are disjoint and show that the corresponding decision problem is NP-hard for general graphs.

Published

2011-06-09

How to Cite

Löwenstein, Christian, & Rautenbach, Dieter. (2011). Cohabitation of independent sets and dominating sets in trees. Utilitas Mathematica, 85. Retrieved from https://utilitasmathematica.com/index.php/Index/article/view/768

Issue

Vol. 85 (2011): Volume 85, 2011

Section

Articles

Citation Check

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.