1. Home

Cohabitation of independent sets and dominating sets in trees

Löwenstein, Christian; Rautenbach, Dieter GND

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-complete for general graphs.

Preview

Category

In Series:
Preprint / Technische Universität Ilmenau, Institut für Mathematik
Vol. 08-11 (16.04.2008)
Date Created:
16.04.2008
Date Issued:
16.04.2008
PPN:
562004718
Language:
English
Type of Resource:
Text
Keywords:
domination; independence; inverse domination
Classification:
Klasse A
Classification:
für Harvesting bereitgestellt
DDC subject of DNB:
510 Mathematics
Hosting institution:
Technische Universität Ilmenau, Fakultät für Mathematik und Naturwissenschaften

Cite

Citation style:

Löwenstein, Christian / Rautenbach, Dieter: Cohabitation of independent sets and dominating sets in trees. 2008.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

open graphic

Rights

Use and reproduction:
All rights reserved

Export

BibTeX, MODS, MARCXML, RIS, ISI, PICA, CSV, DC