半電力控制集的研究

Abstract

用圖的模型來研究一個半電力控制集問題是在圖G上一些點放著測試器，依據我們訂下的規則，若能讓圖G的所有邊都被觀察到，則我們稱這些點所成的集合為圖G的半電力控制集合。在這篇論文中，我們先說明了電力控制集問題與半電力控制集問題的關聯性。接著，我們證明了一些特殊圖的半電力控制集的最少點數，也證明當圖G為連通圖，且G中每個點所連到的邊數至少為兩邊時，半電力控制集的最少點數與回饋點集的最少點數相等。我們也提出一遞迴方法，來建構PnXPn、CnXCn的半電力控制集；於是，提供了一個半電力控制集最少點數的上界。最後我們證出PnXPn的半電力控制集最少點數為Fn或Fn+1，其中Fn=[n^2-2n+2]+1，這結果改善了原來文獻中的最佳結論。

In a semi-power domination set (SPDS) system, we place measurement units on some vertices of a graph G, and according to the rule we defined, if all the edges of G can be observed, then we say that the vertex set is a semi-power domination set. In this thesis, we first find the relationship between PDS and SPDS, and then we prove that the minimum size of SPDS of a graph G, denoted by γsp(G) is equal to the minimum size of the feedback vertex set of G provided G is connected and δ(G)≧2. In addition, we bring up a recursive idea to produce the SPDS of a graph G. Finally, with the recursive idea, we prove that γsp(PnXPn) is equal to either Fn or Fn+1 where Fn=[n^2-2n+2]+1. This improves known results.