臺灣博碩士論文加值系統

用圖的模型來研究一個半電力控制集問題是在圖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.

Contents
摘要..................................... I
Abstract ............................... II
1. Introduction and Preliminaries ...... 1
1.1. Graph Notions ...................... 1
1.2. Power-dominating Sets .............. 4
1.3. Semi-power Dominating Sets ......... 5
1.4. Feedback Vertex Sets ............... 7
2. Known Results ........................ 8
2.1. On Power-dominating Sets............ 8
2.2. On Feedback Vertex Sets ............ 9
3. Main Results ........................ 12
4. Concluding Remark ................... 19
References ............................. 20

[1] T. L. Baldwin, L. Mili, M. B. Boisen, Jr., and R. Adapa, Power system observability with minimal phasor measurement placement, IEEE Transactions on Power Systems, 8(2) (1993), 707 – 715.
[2] M. B. Boisen, Jr., T. L. Baldwin, and L. Mili, Simulated annealing and graph theory applied to electrical power networks, manuscript, 2000.
[3] D. J. Brueni, Minimal PMU placement for graph observability: A Decomposition Approach, Master thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, 1993.
[4] D. J. Brueni and L. S. Heath, The PMU placement problem, SIAM J. Discrete Math., 19(3) (2005), 744 – 761.
[5] I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos, New bounds on the size of the minimum feedback vertex set in meshes and butterflies, Inform. Process. Lett., 83 (2002), 275 – 280.
[6] C.-C. Chuang, Study on power domination of graphs, Master Thesis, National Taiwan University, Taipei, Taiwan, 2008.
[7] W.J. Dally and B. Towles, Principles and practices of interconnection networks, Morgan Kaufmann, Los Altos, CA, 2004.
[8] M. Dorfling and M. A. Henning, A note on power domination in grid graphs, Discrete Applied Math., 154 (2006), 1023 – 1027.
[9] G. Fertin, E. Godard, and A. Raspaud, Minimum feedback vertex set and acyclic coloring, Inform. Process. Lett., 84 (2002), 131 – 139.
[10] P. Festa, P.M. Pardalos, and M.G.C. Resende, Feedback set problems, in: D.Z. Du, P.M. Pardalos (Eds.), in: Handbook of combinatorial optimization (Suppl.), Vol. A, Kluwer Academic Publishers, Dordrecht, 1999, pp. 209 – 258.
[11] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
[12] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, eds., Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[13] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and M. A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Math., 15(4) (2002), 519 – 529.
[14] R. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85 – 103.
[15] F.L. Luccio, Almost exact minimum feedback vertex sets in meshes and butterflies, Inform. Process. Lett., 66 (1998), 59 – 64.
[16] F. R. Madelaine and I. A. Stewart, Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies, Discrete Math., 308 (2008), 4144 – 4164.
[17] L. Mili, T. Baldwin, and A. Phadke, Phasor measurement placement for voltage and stability monitoring and control, in Proceedings of the EPRI-NSF Workshop on Application of Advanced Mathematics to Power Systems, San Francisco, CA, 1991.
[18] D. B. West, Introduction to graph theory, Upper Saddle River, NJ: Prentice Hall. (2001).
[19] M. Zhao, L. Kang and G. J. Chang, Power domination in graphs, Discrete Math., 306 (2006), 1812 – 1816.