|
چکیده
|
The set � of the vertices of a graph � = (�, �) is called a dominating set, if each vertex � ∈ �\� is adjacent with a vertex in �. The cardinality of a dominating set in � with minimum number of vertices is called the domination number of � and it is denoted by �(�). The set � of the vertices of a graph � = (�, �) is called a total dominating set, if each vertex � ∈ � is adjacent with at least one vertex in �. In other words, � is a total dominating set, if (i) � is a dominating set, (ii) for each vertex � ∈ �, there exists another vertex �′ ∈ � adjacent to �. The cardinality of a total domination set in � with minimum number of vertices is called the total domination number of � and denoted by ��(�) A set � ⊆ � from � = (�, �) is called connected dominating set, if (i) D is a dominating set, (ii) the subgraph induced by � denoted by < � > is connected. The cardinality of the minimum connected dominating set is connected domination number and it is denoted by ��(�). The importance of dominating set is discussed in chemical structures. For example, if �� is a hexagonal chain of dimension � , �(��) is the dominating number and ��(��) is the independent dominating number, then, we show that the following equality holds: �(��) = ��(��) = � + ⌊�6⌋ + 1, Let � be a subset of vertices in the connected graph �(�, �). We say, the set �(�) is an observed set by � whenever it satisfies the following recurrence relations: (domination) �(�) ≔ � ∪ �(�), where �(�) consists the neighborhood of �. (propagation) While there is � ∈ �(�) such that � ∈ (�(�) − �(�)) ∩ �(�), set �(�) ≔ �(�) ∪ {�}.
|