- Tytuł:
- Connected odd dominating sets in graphs
- Autorzy:
-
Caro, Yair
Klostermeyer, William
Yuster, Raphael - Powiązania:
- https://bibliotekanauki.pl/articles/744351.pdf
- Data publikacji:
- 2005
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
dominating set
odd dominating set - Opis:
- An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there are only 15 grid graphs that have a connected odd dominating set.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 225-239
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł