# Definitions for dominating setdom·i·nat·ing set

### WiktionaryRate this definition:0.0 / 0 votes

1. dominating setnoun

A set of vertices of a graph, such that each vertex in that graph is either in that set or adjacent to some vertex in that set.

### WikipediaRate this definition:0.0 / 0 votes

1. Dominating set

In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there may be no efficient algorithm that can compute γ(G) for all graphs G. However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes. Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad-hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids.

### WikidataRate this definition:0.0 / 0 votes

1. Dominating set

In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number γ is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether γ ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory. Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph. Figures – on the right show three examples of dominating sets for a graph. In each example, each white vertex is adjacent to at least one red vertex, and it is said that the white vertex is dominated by the red vertex. The domination number of this graph is 2: the examples and show that there is a dominating set with 2 vertices, and it can be checked that there is no dominating set with only 1 vertex for this graph.

### Numerology

1. Chaldean Numerology

The numerical value of dominating set in Chaldean Numerology is: 2

2. Pythagorean Numerology

The numerical value of dominating set in Pythagorean Numerology is: 6

## Translations for dominating set

### From our Multilingual Translation Dictionary

• dominierende Menge

### Translation

#### Find a translation for the dominating set definition in other languages:

Select another language:

• - Select -
• 简体中文 (Chinese - Simplified)
• Español (Spanish)
• Esperanto (Esperanto)
• 日本語 (Japanese)
• Português (Portuguese)
• Deutsch (German)
• العربية (Arabic)
• Français (French)
• Русский (Russian)
• 한국어 (Korean)
• עברית (Hebrew)
• Gaeilge (Irish)
• Українська (Ukrainian)
• اردو (Urdu)
• Magyar (Hungarian)
• मानक हिन्दी (Hindi)
• Indonesia (Indonesian)
• Italiano (Italian)
• தமிழ் (Tamil)
• Türkçe (Turkish)
• తెలుగు (Telugu)
• ภาษาไทย (Thai)
• Tiếng Việt (Vietnamese)
• Čeština (Czech)
• Polski (Polish)
• Bahasa Indonesia (Indonesian)
• Românește (Romanian)
• Nederlands (Dutch)
• Ελληνικά (Greek)
• Latinum (Latin)
• Svenska (Swedish)
• Dansk (Danish)
• Suomi (Finnish)
• فارسی (Persian)
• ייִדיש (Yiddish)
• հայերեն (Armenian)
• Norsk (Norwegian)
• English (English)

## Citation

#### Use the citation below to add this definition to your bibliography:

Style:MLAChicagoAPA

"dominating set." Definitions.net. STANDS4 LLC, 2024. Web. 8 Aug. 2024. <https://www.definitions.net/definition/dominating+set>.

## Are we missing a good definition for dominating set? Don't keep it to yourself...

### dominating set

Credit »

#### Free, no signup required:

Get instant definitions for any word that hits you anywhere on the web!

#### Free, no signup required:

Get instant definitions for any word that hits you anywhere on the web!

### Quiz

#### Are you a words master?

»
##### (of a flowering plant) having two cotyledons in the seed
A dicotyledonous
B inexpiable