Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
minimum dominating set code matlab
#1

In graph theory, a dominating set for a graph G = (V, E) 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 (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 (Garey & Johnson 1979). Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph.

Figures (a) © 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 (b) 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.
As Hedetniemi & Laskar (1990) note, the domination problem was studied from the 1950s onwards, but the rate of research on domination significantly increased in the mid-1970s. Their bibliography lists over 300 papers related to domination in graphs.

Bounds[edit]
Let G be a graph with n 1 vertices and let be the maximum degree of the graph. The following bounds on (G) are known (Haynes, Hedetniemi & Slater 1998a, Chapter 2):

One vertex can dominate at most other vertices; therefore (G) n/(1 + ).
The set of all vertices is a dominating set in any graph; therefore (G) n.
If there are no isolated vertices in G, then there are two disjoint dominating sets in G; see domatic partition for details. Therefore in any graph without isolated vertices it holds that (G) n/2.
Independent domination[edit]
Dominating sets are closely related to independent sets: an independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set. Thus, the smallest maximal independent set is greater in size than the smallest independent dominating set. The independent domination number i(G) of a graph G is the size of the smallest independent dominating set (or, equivalently, the size of the smallest maximal independent set).

The minimum dominating set in a graph will not necessarily be independent, but the size of a minimum dominating set is always less than or equal to the size of a minimum maximal independent set, that is, (G) i(G).

There are graph families in which a minimum maximal independent set is a minimum dominating set. For example, Allan & Laskar (1978) show that (G) = i(G) if G is a claw-free graph.

A graph G is called a domination-perfect graph if (H) = i(H) in every induced subgraph H of G. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect (Faudree, Flandrin & Ryj ek 1997).
Reply

#2
In graph theory, a dominating set for a graph G = (V, E) 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 (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 (Garey & Johnson 1979). Therefore it is believed that there is no efficient algorithm that finds a smallest dominating set for a given graph.

Figures (a) © 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 (b) 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.
Dominating sets are closely related to independent sets: an independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set. Thus, the smallest maximal independent set is greater in size than the smallest independent dominating set. The independent domination number i(G) of a graph G is the size of the smallest independent dominating set (or, equivalently, the size of the smallest maximal independent set).

The minimum dominating set in a graph will not necessarily be independent, but the size of a minimum dominating set is always less than or equal to the size of a minimum maximal independent set, that is, (G) i .

There are graph families in which a minimum maximal independent set is a minimum dominating set. For example, Allan & Laskar (1978) show that (G) = i(G) if G is a claw-free graph.

A graph G is called a domination-perfect graph if (H) = i(H) in every induced subgraph H of G. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graphs is also domination-perfect (Faudree, Flandrin & Ryj ek 1997).
Reply

#3
hi i am nandhini,i am doindg my project in "evaluation of routing performance in manet using domination set" ,plz i need a code for this project,its very urgent.
thanks in advance.
Reply

#4

hi
i need a coding for "evaluation of routing performance in manet using domination set(adjacency matrix approach)".

thank u
Reply



[-]
Quick Reply

Forum Jump:


Users browsing this thread:
1 Guest(s)

Powered By MyBB, © 2002-2024 iAndrew & Melroy van den Berg.