Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Exact double domination in graphs

100%

Chellali M., Khelladi A., Maffray F.

Discussiones Mathematicae Graph Theory

2005

tom 25

nr 3

291-302

In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive characterization of those trees that admit a doubly dominating set, and we establish a necessary and sufficient condition for the existence of an exact doubly dominating set in a connected cubic graph.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Chellali M.

1 Khelladi A.

1 Maffray F.

1 2005

Wyniki wyszukiwania

Exact double domination in graphs