臺灣博碩士論文加值系統

給定一個圖G，V(G)和E(G)分別為圖G的點集合及邊集合。為了簡化符號我們用V和E來取代V(G)和E(G)。圖G上的一組支配集D必須滿足以下條件：D包含於或等於V且對於每個不在D中的點至少要與一個D中的點相鄰。支配集問題以及此問題的變形有許多豐富的延伸研究，例如獨立支配、彩虹支配、全部支配、羅馬支配等等，這些變形的支配集問題除了要符合支配集的性質外並再加上一些限制條件。在本研究計畫中，我們將探討一個新的支配集變形問題稱作外配對支配集問題。問題定義如下: 在一個圖G=(V,E)上的一組外配對支配集D必須滿足下列條件：D必須為一個支配集，而且V\D形成的子圖必須有完美配對。外配對支配集問題是找出一組點數最少的外配對支配集。在本論文中，我們提供一個時間複雜度為O(n)的演算法來解決真區間圖中的外配對支配集問題，其中n為圖G中點的個數。

Let G=(V,E) be an undirected graph, where V(G) and E(G) are vertex and edge sets of G, respectively. For simplicity, we also use V and E to represent V(G) and E(G), respectively. For any vertex vV , the open neighborhood of v is the set NG(v) = {uV : uv E}. The closed neighborhood of v is NG[v] = NG(v){v}. For simplicity, NG(v) and NG[v] are simply written as N(v) and N[v], respectively. A set D is a dominating set of a graph G if every vertex in V\D is adjacent to at least one vertex in D. The domination problem and its variants were extensively studied, e.g., independent domination, rainbow domination, total domination, roman domination, etc. We can find that all variants on the domination problem are adding some constraints to the domination problem. In this thesis, we investigate a new variant of the domination problem called the outer-paired domination problem which is defined as follows. An outer-paired domination set (OPD-set for short) of a graph G is a dominating set D of G such that the induced subgraph of V\D contains a perfect matching. In this thesis, we propose an O(n)-time algorithm for solving the outer-paired domination problem on proper interval graphs, where n is the number of vertices in V .

1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problem Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.4 The organization of this thesis . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Preliminaries 3
2.1 Some related graph classes and properties . . . . . . . . . . . . . . . . . . . 3
3 Main results 6
4 Concluding Remarks 13
4.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
References 14

[1] M.H. Akhbari, R. Hasni, O. Favaron, H. Karami, and S.M. Sheikholeslami, On the outer-connected domination in graphs, Journal of Combinatorial Optimization 26 (2013) 10-18.
[2] R.B. Allan and R.C. Laskar, On domination and independent domination numbers of a graph, Discrete Mathematics 23 (1978) 73-76.
[3] John Adrian Bondy and U.S.R. Murty, Graph Theory with Applications, 1977.
[4] B. Bresar and T.K. Sumenjak, On the 2{rainbow domination in graphs, Discrete Applied Mathematics 155 (2007) 2394-2400.
[5] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi, Total domination in graphs, Net-works 10 (1980) 211-219.
[6] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi, and S.T. Hedetniemi, On Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22.
[7] J. Cyman, The outer-connected domination number of a graph, The Australasian Journal of Combinatorics 38 (2007) 35-46.
[8] J.F. Fink and M.S. Jacobson, n-domination in graphs, Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons, New York (1985), 282-300.
[9] H. Jiang and E. Shan, Outer-connected domination in graphs, Utilitas Mathematica 81 (2010) 265-274.
[10] J.M. Keil and D. Pradhan, Computing a minimum outer-connected dominating set for the class of chordal graphs, Information Processing Letters 113 (2013) 552-561.
[11] Ching-Chi Lin and Cheng-Yu Hsieh, Linear-Time Algorithm for the Paired-Domination Problem on Weighted Block Graphs, The 32nd Workshop on Combinatorial Mathematics and Computation Theory.
[12] Chih-Yuan Lin, Jia-Jie Liu, Yue-Li Wang and Chiun-Chieh Hsu, Dominating Sets with Matching Outside, The 32nd Workshop on Combinatorial Mathematics and Computation Theory (2015) 71-76.
[13] D.B. West, Introduction to Graph Theory.(2nd ed.), River, N.J.: Prentice-Hall, 2001.