臺灣博碩士論文加值系統

給定一個圖形G和一個子集合S包含於V(G)，一個點v如果滿足下列條件之一的話就稱為被S中的一點w做F控制
(1)如果v=w
(2)如果v不在S中而且可以找到另外一點u也不在S中使得P: wuv會形成一條G中的路徑。此外一個V(G)中的子集合S如果滿足V(G)中的任何一點v都可以被S中的某一點w做F控制，則S被稱為是G中的一個F控制集。
因此我們可以考慮圖形G中的所有F控制集；並且定義G的F控制數為具有最少點數的F控制集大小，另外使用符號rf(G)代表此數。在這篇文章中我們考慮圖形的F控制問題。我們證明了圖形上的F控制問題是一個NP-complete的問題，而且對於特定的m與n值我們給出了一些公式方便計算Pm*Pn 和Pm*Cn的F控制數。 最後我們也證明出對於generalized Petersen graph的確切F控制數。

Given a graph G and a set S⊆V(G), a vertex v is said to be F-dominated by a vertex w in S if either v=w, or v∉S and there exists a vertex u in V(G)-S such that P:wuv is a path in G. A set S⊆V(G) is an F-dominating set of G if every vertex v is F-dominated by a vertex w in S. The F-domination number of G, denoted by γ_{F}(G), is the minimum cardinality of an F-dominating set of G. We consider the F-domination problem of graphs in this thesis. We prove that the F-domination problem is an NP-complete problem and give formulas to compute the F-domination number of P_{m}×P_{n} and P_{m}×C_{n} for special m,n. And we also give a formula to compute the F-domination number of the generalized petersen graph P(n,2) for all n≥12.

1 Introduction ……………………… 01

2 Preliminary ……………………… 11

3 NP-Complete ……………………… 14

4 Cartesian Product ……………………… 18

5 Generalized Petersen graphs ……………………… 31

[1] S. A. Cook, The complexity of theorem-proving procedures, Proc. 3rd Ann. ACM Symp. on Theory of Computing, (1971), 151-158.
[2] G. Chartrand, T. W. Haynes, M. A. Henning, P. Zhang, Stratification and domination in graphs, Discrete Math. 272 (2003), 171-185.
[3] E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980), 211-219.
[4] G. S. Domke, J. H. Hattingh, M. A. Henning, L. R. Markus, Restrained domination in graphs with minimum degree two, J. Combin. Math. Combin. Comput. 35 (2000), 239-254.
[5] J. F. Fink, M. S. Jacobson, n-domination in graphs, in: Y. Alavi, A.J. Schwenk (Eds.), Graph Theory with Applications to Algorithms and Computer Science,(Kalamazoo, MI 1984), Wiley, New York, 1985, pp. 283-300.
[6] M. R. Garey and D. S. Johnson, Computer and Intractability-A Guide to the Theory of NP-Completeness, (1979).
[7] R. Gera, P. Zhang, Bounds for the F-domination number of a graph, Congr. Numer. 166 (2004), 131-144.