標題: 半電力控制集的研究
A Study of Semi-power Dominating Set
作者: 吳政軒
傅恆霖
應用數學系所
關鍵字: 電力控制集;半電力控制集;回饋點集合;power dominating set;semi-power dominating set;feedback vertex set
公開日期: 2009
摘要: 用圖的模型來研究一個半電力控制集問題是在圖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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079522531
http://hdl.handle.net/11536/41202
Appears in Collections:Thesis


Files in This Item:

  1. 253101.pdf
  2. 253101.pdf