臺灣博碩士論文加值系統

圖 G = (V, E) 的一個正負支配函數(Signed Domination Function) f會將圖G的所有點給予值 1 或 —1 讓每個點與它的所有鄰居的值的和加起來會大於等於1。若圖G上的每一個點和它的鄰居的值的和加起來都剛好是1，則稱 f 為有效率的正負支配函數(Efficient Signed Dominating Function)。
一般圖上，這兩個問題是NP-complete的問題。因此，
我們將這些問題放在互補圖(Cograph)上討論。在這篇論文中，我們利用動態規劃(Dynamic Programming)法給予兩個時間複雜度 (Time Complexity) 為O(n5) 的演算法來解決互補圖上的正負支配問題和有效率的正負支配問題。

A signed dominating function of a graph G = (V, E) is defined as a function f : V -> {-1, 1} such that sum (s in N[v] f(s))
> = 1, where N[v] consists of v and every vertex adjacent to v. We say a signed dominating function f is an efficient signed dominating function if the closed neighborhood sum is exactly 1 at every vertex. These two problems are NP-complete for general graphs, hence we focus on cographs. A graph is called a cograph if it does not contain a path linking four vertices as an induced subgraph. In this thesis, we present two O(n5) algorithms to solve the signed domination and the efficient signed domination on cographs by using dynamic programming approach.

1 Introduction 1
2 Preliminaries 4
3 Signed domination on cographs 8
4 EÆcient signed domination on cographs 17
5 Conclusions 24
A Reference 25

[1] D. W. Bange, A. E. Barkauskas, P. J. Slater, L. H. Host,
Generalized domination and efficient domination in graphs,
Discrete Math., 159 (1996), pp.1-11
[2] D. G. Corneil, H. Lerchs, L. S. Burlingham,
Complement reducible graphs,
Discrete Appl. Math., 3 (1981), pp.163-174
[3] D. G. Corneil, Y. Perlm L. K. Stewart,
A linear recognition algorithm for cographs,
SIAM J. Comput., 14 (1985), pp.926-934
[4] J. E. Dunbar, S. T. Hedetniemi, M. A. Henning, P. J.Slater,
Signed domination in graphs, Graph Theory, Combinatorics,
and Applications, John Wiley & Sons, Inc., 1 (1995), pp.
311-322
[5] O. Favaron, Signed domination in regular graphs,
Discrete Math., 158 (1996), pp. 287-293
[6] J. H. Hattingh, M. A. Henning, P. J. Slater,
On the algorithmic complexity of signed domination in
graphs, Australas. J. Combin., 12 (1995), pp. 101-112
[7] M. A. Henning, P. J. Slater,
Inequalities relating domination parameters in cubic
graphs, Discrete Math., 158 (1996), pp. 87-98
[8] H. A. Jung, On a class of posets and the corresponding
comparability graphs, Journal of Combinatorial Theory (B),
24 (1978), pp. 125-133
[9] H. Lerchs, On the clique-kernel structure of graphs, a
manuscript, Department of Computer Science, University of
Toronto (October 1972).
[10] R. Lin, S. Olariu, G. Pruesse,
An optimal path cover algorithm for cographs,
Computers Math. Applic. 30, 8 (1995), pp. 75-83
[11] C. M. Liu, M. S. Yu,
An optimal parallel algorithm for node ranking of
cographs, Discrete Appl. Math., 87 (1998), pp. 187-201
[12] C. L. Lu, S. L. Peng C. Y. Tang,
Efficient minus and signed domination in graphs,
Lecture Notes in Computer Science, 1969 (2000), pp.241-253
[13] D. Seinsche,
On a property of the class of n-colorable graphs,
Journal of Combinatorial Theory (B), 16 (1974), pp.191-193
[14] D. P. Sumner, Dacey graphs,
Journal of the Australian Math. Society, 18 (1974), pp.
492-502