Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Connected odd dominating sets in graphs

100%

Caro Y., Klostermeyer W., Yuster R.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 3

225-239

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Caro Y.

1 Klostermeyer W.

1 Yuster R.

1 2005

Wyniki wyszukiwania

Connected odd dominating sets in graphs