臺灣博碩士論文加值系統

給定一個圖G=(V,E)，全支配集是指在圖G中存在一個點集合V的子集合D，而在V中所有的點都必須與D中的點相鄰。分離性全支配集是指在圖G中存在一個點集合V的子集合D，而V中所有的點都必須至少與D中的一點相鄰或者與D中的兩個點之間距離為二。分離性全支配問題就是找出圖G最小的分離性全支配集D。而圖G中最小的分離性全支配集稱為圖G的分離性全支配數。在這篇論文中，我們探討分離性全支配問題在格子圖與環面上之研究。而在某些特殊例子當中，我們所提出的解剛好會是其最佳解。

For a graph G = (V;E), a subset D of V is a total dominating set of
G if every vertex in V has to be adjacent to a vertex of D. Vertex
subset D is a disjunctive total dominating set if every vertex of V is
adjacent to a vertex of D or has at least two vertices in D at distance 2 from it. The disjunctive total domination problem on G is to find a disjunctive total dominating set D of the minimum cardinality. The cardinality of a minimum disjunctive total dominating set of G is called the disjunctive total domination number of G. In this thesis, we study the disjunctive total domination problem on grid graphs and tori. We propose upper bounds for general grid graphs and tori. In particular, some bounds are optimal for some special cases.

1 Introduction
2 Disjunctive Total Domination on Grid Graphs
3 Disjunctive Total Domination on Tori
4 Conclusion and Future Work

[1] Booth, K.S., Johnson, J.H.: Dominating sets in chordal graphs. SIAM J. Com-put. 11, 191-199 (1982)
[2] Chang, G.J.: Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Applied Mathematics 22, 21-34 (1988)
[3] Chellali, M., Haynes, T.W.: A note on the total domination number of a tree.J. Combin. Math. Combin. Comput. 58, 189-193 (2006)
[4] Crevals, S., stergrd, P.R.J.: Independent domination of grids. Discrete Mathe-matics 338, 1379-1384 (2015)
[5] Delavina, E., Pepper, R.; Waller, B.: Lower bounds for the domination number.Discussiones Mathematicae Graph Theory 30, 475-487 (2010)
[6] Favaron, O., Henning, M.A.: Total domination in claw-free graphs with minimum degree 2. Discrete Mathematics 308(15), 3213-3219 (2008)
[7] Flandrin, E., Faudree, R., Ryjcek, Z.: Claw-free graphs - a survey. Discrete Math.164(1-3), 87-147 (1997)
[8] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA (1979)
[9] Goddard, W., Henning, M.A., McPillan, C.A.: The disjunctive domination num-ber of a graph. Quaestiones Math. 37, 547-561 (2014)
[10] Goncalves, D., Pinlou, A., Rao, M., Thomasse, S.: The domination number of grids. SIAM Journal on Discrete Mathematics 25, 1443-1453 (2011)
[11] Gravier, S.: Total domination number of grid graphs. Discrete Applied Mathe-matics 121, 119-128 (2002)
[12] Henning, M.A.: Graphs with large total domination number. Journal of Graph Theory 35, 21-45 (2000)
[13] Henning, M.A.: A survey of selected recent results on total domination in graphs.Discrete Mathematics 309, 32-63 (2009)
[14] Henning, M.A., Marcon, S.A.: Domination versus disjunctive domination in trees. Discrete Applied Mathematics 184, 171-177 (2015)
[15] Henning, M.A., Marcon, S.A.: Domination versus disjunctive domination in graphs. Quaestiones Mathematicae 39, 261-273 (2016)
[16] Henning, M.A., Naicker, V.: Graphs with large disjunctive total domination number. Discrete Mathematics & Theoretical Computer Science 17, 255-282(2015)
[17] Henning, M.A., Naicker, V.: Bounds on the disjunctive total domination number of a tree. Discussiones Mathematicae Graph Theory 36, 153{171 (2016)
[18] Henning, M.A., Naicker, V.: Disjunctive total domination in graphs. J. Comb.Optim. 31, 1090{1110 (2016)
[19] Henning, M.A., Yeo, A.: Total Domination in Graphs. Springer-Verlag New York, isbn=978-1-4614-6525-6 (2013)
[20] Keil, J.M.: The complexity of domination problems in circle graphs. Discrete Applied Mathematics 42, 51{63 (1993)
[21] Klaviar, S., Seifter, N.: Dominating Cartesian products of cycles, Discrete Appl.Math. 59, 129-136 (1995)
[22] Kratsch, D., Stewart, L.: Total domination and transformation. Inf. Process.Lett. 63, 167{170 (1997)
[23] Laskar, R., Pfa, J., Hedetniemi, S.M., Hedetneimi, S.T.: On the algorithmic complexity of total domination. SIAM J. on Algebraic and Discrete Methods 5,420-425 (1984)
[24] Lin, C.-F., Peng, S.-L.: Algorithmic aspects of disjunctive total domination in graphs. Proceedings of the 10th International Conference on Combinatorial Op-timization and Applications (COCOA 2016), 285{293 (2016)
[25] Panda, B.S., Pandey, A., Paul, S.: Algorithmic aspects of disjunctive domination in graphs. Proceedings of COCOON 2015, 325-336 (2015)
[26] Ramalingam, G., Rangan, C.P.: Total domination in interval graphs revisited.Inf. Process. Lett. 27, 17-21 (1988)
[27] Telle, J.A.: Complexity of domination-type problems in graphs. Nord. J. Com-put. 1, 157-171 (1994)