臺灣博碩士論文加值系統

圖形G的負支配函數是將G中所有點給予一個值1、0或-1，使得每個點與它所有連接點的函數值總和會大於或等於1，而圖形G的符號支配函數則是將G中所有點給予一個值1或-1，使得每個點與它所有連接點的函數值總和會大於或等於1。不論是負支配函數或符號支配函數，其所有點的函數值總和皆稱之為該函數的權重。負支配問題和符號支配問題，其目的便是找出圖形中權重最小的負支配函數和符號支配函數。本論文主要探討負支配問題和符號支配問題的變形問題，例如：符號k支配問題、反置符號支配問題、反置負支配問題。本論文成果如下：
證明即使k是常數並且將圖形限制在雙弦圖或二分平面圖上，符號k支配問題依然是NP完備問題，而且不屬於固定參數複雜度。
證明即使k是常數並且將圖形限制在弦圖或二分平面圖上，反置負支配問題依然是NP完備問題。除此之外，亦證明即使將圖形限制在雙弦圖或二分平面圖上，反置符號k支配問題依然是NP完備問題，而且不屬於固定參數複雜度。
在強弦圖和保距圖上，設計多項式演算法解決符號k支配問題、反置符號支配問題、反置負支配問題。除此之外，證明在樹圖、區間圖、弦比較圖上，這三個問題皆可在線性時間內解決。

A minus (respectively, signed) dominating function of a graph G = (V, E) is a function f：V → {-1, 0, 1} (respectively, {-1, 1}) such that Σu∈N_G[v] f(u) ≥ 1 for all v ∈ V , where N_G [v] = {v}⋃{u|(u, v) ∈ E}. The weight of a minus (respectively, signed) dominating function of G is the sum of its function values over all vertices. The minus respectively, signed) domination problem is to find a minus (respectively, signed) dominating function of G of minimum weight. In this thesis, we study some variations of the signed domination and minus domination problems such as the signed k-domination, reverse signed domination, and reverse minus domination problems. The results of the thesis are as follows：
Let k be a fixed nonnegative integer. For doubly chordal graphs and bipartite planar graphs, we show that the signed k-domination problem is NP-complete. We also show that the signed k-domination problem is not fixed parameter tractable.
For chordal graphs and bipartite planar graphs, we show that the reverse minus domination problem is NP-complete. For doubly chordal graphs and bipartite planar graphs, we show that the reverse signed domination problem is NP-complete. Furthermore, we show that even when restricted to bipartite planar graphs or doubly chordal graphs, the reverse signed domination problem is not fixed parameter tractable.
For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination, reverse signed domination, and reverse minus domination problems can be solved in polynomial time. We also show that these three problems are linear-time solvable for trees, interval graphs, and chordal comparability graphs.

Contents i
List of Tables ii
List of Figures iii
1 Introduction 1
2 Literature Review 3
2.1 Graph Terminology 3
2.2 Special Graphs 4
2.3 The Signed k-Domination Problem 7
2.4 The Reverse Signed Domination Problem 7
2.5 The Reverse Minus Domination Problem 8
3 Results of the thesis 10
4 The Results on Signed k-domination 11
4.1 Doubly Chordal Graphs 11
4.2 Bipartite Planar Graphs 13
4.3 Strongly Chordal Graphs 15
4.4 Trees, Interval Graphs, and Chordal Comparability Graphs 17
4.5 Distance-Hereditary Graphs 18
4.6 Signed k-domination is not Fixed Parameter Tractable 20
5 The Results on Reverse Minus Domination and Reverse Signed Domination 22
5.1 Bipartite Planar Graphs and Doubly Chordal Graphs 22
5.2 Strongly Chordal Graphs 26
5.3 Distance-Hereditary Graphs 27
5.4 Reverse Signed Domination is not Fixed Parameter Tractable 31
References 32

[1] D.W. Bange, A.E. Barkauskas, L.H. Host, and P.J. Slater, Generalized domination and efficient domination in graphs, Discrete Math., 159 (1996) 1–11.
[2] A.A. Bertossi, Dominating sets for split and bipartite graphs, Inform. Process. Lett., 19(1) (1984) 37–40.
[3] S. Booth and S. Lueker, Testing for the Consecutive Ones Property, Interval Graphs, Graph Planarity Using PQ-Trees Algorithms. Journal of Computer and System Sciences, 13 (1976), pp. 335–379.
[4] R.B. Borie and J.P. Spinrad, Construction of a Simple Elimination Scheme for a Chordal Comparability Graph in Linear Time. Discrete Applied Mathematics, 91 (1999), pp. 287–292.
[5] A. Brandst¨adt, F.F. Dragan, V.D. Chepoi, and V. Voloshin, Dually chordal graphs, SIAM J. Discrete Math., 11 (1998) 437–455.
[6] A. Brandst¨adt, V.B. Le, and J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia 1999.
[7] M.S. Chang, S.Y. Hsieh, and G.H. Chen, Dynamic programming on distance-hereditary graphs, in: Proceedings of the 8th International Symposium on Algorithms and Computation, LNCS 1350, pp. 344–353, 1997.
[8] G.J. Chang, Algorithmic aspects of domination in graphs, in: D.Z. Du, P.M. Pardalos (Eds.), Handbook of Combinatorial Optimization, Vol. 3, Kluwer, Boston, MA, 1998, pp. 339–405.
[9] Y.M. Chen, The fault tolerant domination problem on strongly chordal graphs, Master Thesis, National Chung Cheng University, Taiwan, July 2001.
[10] L. Cai, J. Chen, R.G. Downey and M.R. Fellows, Advice Classes of Parameterized Tractability. Annals of Pure and Applied Logic, 84 (1997), pp. 119–138.
[11] P. Damaschke, Minus domination in small-degree graphs, Discrete Applied Mathematics, 108 (2001) 53–64.
[12] R.G. Downey and M.R. Fellows, Parameterized complexity, Monographs in Computer Science, Springer-Verlag, 1999.
[13] J. Dunbar, S.T. Hedetniemi,M.A. Henning and P.J. Slater, Signed Domination in graphs, eds. Y. Alavi and A. Schwenk, Graph theory, Combinatorics, and Applications, (Wiley, New York, 1995) 311–321.
[14] J. Dunbar, W. Goddard, S. Hedetniemi, A. McRae, and M.A. Henning, The algorithmic complexity of minus domination in graphs, Discrete Appl. Math., 68 (1996) 73–84.
[15] J. Dunbar, S.T. Hedetniemi,M.A. Henning, and A.McRae,Minus domination in graphs, Discrete Math., 199 (1999) 35–47.
[16] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173–189.
[17] L. Faria, W.-K. Hon, T. Kloks, H.-H. Liu, T.-M.Wang, Y.-L.Wang, On Complexities of Minus Domination, in: Proceedings of Combinatorial Optimization and Applications - 7th International Conference, COCOA 2013, Lecture Notes in Computer Science 8287,
pp. 178-189.
[18] O. Favaron, Signed domination in regular graphs, Discrete Math.,185 (1996) 287–293.
[19] W. Goddard,M.A. Henning, Real and integer domination in graphs, Discrete Math., 199 (1999), 61–75.
[20] H.J. Gong, Signed domination number in block graphs,Master Thesis, National Central University, Taiwan, June 2004.
[21] M.A. Henning, P.J. Slater, Inequalities relating domination parameters in graphs, Discrete Math., 158 (1996), no.1-3, 87–98.
[22] J.H. Hattingh, M.A. Henning and P.J. Slater, The Algorithmic Complexity of Signed Domination in Graphs. Australasian Journal of Combinatorics, 12 (1995), pp. 101–112.
[23] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[24] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[25] Z. Huang, W. Li, Z. Feng, and H. Xing, On nonnegative signed domination in graphs and its algorithmic complexity, Journal of Networks, 8 (2013) pp.365–372.
[26] C.-M. Lee and M.-S. Chang, Variations of Y-dominating functions on graphs, Discrete Mathematics 308 (2008), pp. 4185-4204.
[27] C.-M. Lee, Remarks on the complexity of non-negative signed domination, Journal of Networks, 9 (2014), pp. 2051–2058.
[28] W. Li, Z. Huang, Z. Feng, and H. Xing, On reverse signed domination in graphs and algorithmic complexity, Journal of Convergence Information Technology, 7 (2012), 324–331.
[29] J.Matousek, On the signed domination in graphs, Combinatorica, 20 (2000), no.1, 103–108.
[30] M. Moscarini, Doubly chordal graphs, Steiner trees, and connected domination, Networks, 23 (1993) 59–69.
[31] R. Paige and R.E. Tarjan, Three partition refinement algorithms, SIAM J. Comput., 16 (1987) 973–989.
[32] D.J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32 (1970) 597–609.
[33] J. Sawada and J.P. Spinrad, From a Simple Elimination Ordering to a Strong Elimination Ordering in Linear Time. Information Processing Letters, 86 (2003), pp. 299–302.
[34] J.P. Spinrad,Doubly lexical ordering of dense 0-1 matrices, Inform. Process. Lett., 45 (1993) 229–235.
[35] R.E. Tarjan and M. Yannakakis, Simple linear algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAMJ. Comput., 13 (1984) pp. 566–579.
[36] L. Volkmann and V.E. Zverovich, A disproof of Henning’s conjecture on irredundance perfect grphs, Discrete Mathematics, 254 (2002) 539–554.
[37] Wang, C. (2012) The Signed k-Domination Numbers in Graphs. Ars Combinatoria, 106 (2012), pp.205–211.
[38] H.G. Yeh and G.J. Chang, Algorithmic aspects of majority domination, Taiwanese Journal of Mathematics, 1 (1997), 343–350.
[39] B. Zelinka, Some remarks on domination in cubic graphs, Discrete Math., 158(1996) 249–255.
[40] B. Zelinka, Dominating funcitons of graphs with two values, Math. Bohem., 123 (1998) 263–270.