系統識別號 | U0002-0807201413523400 |
---|---|
DOI | 10.6846/TKU.2014.00216 |
論文名稱(中文) | 羅馬控制數的探討 |
論文名稱(英文) | The study of Roman domination number |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士班 |
系所名稱(英文) | Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 102 |
學期 | 2 |
出版年 | 103 |
研究生(中文) | 許智雄 |
研究生(英文) | Zhi-Xiong Xu |
學號 | 601190142 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2014-06-13 |
論文頁數 | 47頁 |
口試委員 |
指導教授
-
高金美(cmfu@mail.tku.edu.tw)
委員 - 傅恆霖(hlfu@math.nctu.edu.tw) 委員 - 黃明輝(mhhuang@mail.ypu.edu.tw) |
關鍵字(中) |
蜘蛛圖 一般蜘蛛圖 羅馬控制數 |
關鍵字(英) |
spider graph generalized spider graph Roman domination number |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
在一個圖G=(V,E)上, 定義一個函數 f 將V對應到{0, 1, 2},假如f滿足每一個對應到0 的點都有一個對應到2的鄰居,函數 f 稱為羅馬控制函數。函數f的權重為圖中所有點相應的權重總和,而所有可能的羅馬控制函數中權重最小者稱為圖 G 的羅馬控制數。一個蜘蛛圖 G(k_1,k_2,k_3,…,k_t )為含有共同端點的t個路徑〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t )所形成的圖。一個一般蜘蛛圖〖 C〗_t (k_1,k_2,k_3,…,k_t )是由一個迴圈〖 C〗_t=(1,2,3,…,t) 及t個點相異的路徑的聯集,此t個路徑分別與〖 C〗_(t )交於相異的一點且與〖 C〗_(t )交於點i的路徑為〖 P〗_(k_i )。在此論文中,我們分別獲得蜘蛛圖G(k_1,k_2,k_3,…,k_t )之控制數與羅馬控制數的計算方法,進而利用蜘蛛圖之羅馬控制數得到 γ_R (C_3 (k_(1 ), k_2, k_3 )) 以及 γ_R (C_4 (k_1,k_2,k_3,k_4 ))的計算方法,同時獲得〖 γ〗_R (C_5 (n_1,n_2,n_3,n_4,n_5 ))及γ_R (C_6 (n_1,n_2,n_3,n_4,n_5,n_6 ))=γ_R (C_3 (n_1,n_2,n_3 ))+γ_R (C_3 (n_4,n_5,n_6 ))之猜想。 |
英文摘要 |
Given a graph G = (V, E). We define a function f from V to {0, 1, 2}. The function f is called a Roman dominating function on G when satisfying the condition that every vertex v_i with f(v_i)=0 must be adjacent to at least one vertex v_j with f(v_j)=2. The weight of Roman dominating function f is the sum of the weight of each vertex of G. The minimum weight of all possible Roman dominating functions on G is the Roman domination number of G, denoted by γ_R (G). A spider graph G(k_1,k_2,k_3,…,k_t ) is the union of t paths〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t )with one common end vertex. A generalized spider graph〖 C〗_t (k_1,k_2,k_3,…,k_t ) is the union of a t-cycle〖 C〗_t=(1,2,3,…,t) and t paths〖 P〗_(k_1 ), 〖 P〗_(k_2 ), …, 〖 P〗_(k_t ) where each path intersect Ct with exact one vertex and〖 P〗_(k_i ) intersect Ct at the vertex i. In this thesis, we obtain the formula to calculate the minimum domination number and Roman domination number of each spider graph. For the Roman domination number of a generalized spider graph, we obtain the formula of γ_R (C_3 (k_(1 ), k_2, k_3 )) and γ_R (C_4 (k_1,k_2,k_3,k_4 )) related to the Roman domination number of a spider graph. After that we give two conjectures about calculating γ_R (C_5 (n_1,n_2,n_3,n_4,n_5 )) and γ_R (C_6 (n_1,n_2,n_3,n_4,n_5,n_6 )). |
第三語言摘要 | |
論文目次 |
目錄 目錄 1 圖表目錄 2 第一章 簡介 3 第二章 預備知識 7 第三章 蜘蛛圖的控制數與羅馬控制數 16 第四章 一般蜘蛛圖的羅馬控制數 36 參考文獻 47 圖表目錄 圖2.1圖2.2 7 圖2. 3圖2. 4 8 圖2. 5 9 圖2. 6 10 圖2. 7 12 圖2. 8 13 圖2. 9圖2. 10 14 圖2. 11 15 圖3. 1 17 圖3. 2圖3. 3 19 圖3. 4 20 圖3. 5圖3. 6 21 圖3. 7圖3. 8圖3. 9 22 圖3. 10圖3. 11圖3. 12 23 圖3. 13圖3. 14 24 圖3. 15 25 圖3. 16 26 圖3. 17 27 圖3. 18圖3. 19 29 圖3. 20圖3. 21圖3. 22 30 圖3. 23圖3. 24 31 圖3. 25圖3. 26 32 圖3. 27 34 圖4. 1 36 圖4. 2圖4. 3 37 圖4. 4 38 圖4. 5 39 圖4. 6 40 圖4. 7圖4. 8 41 圖4. 9圖4. 10 43 圖4. 11 44 圖4. 12 45 |
參考文獻 |
[1] Erin W. Chambers, Bill Kinnersley, Noah Prince, Douglas B. West, Extremal Problems for Roman Domination ,(2009) [2] E. J. Cockayne, P. A. Jr. Dreyer, S. M., Hedetniemi, and S. T. Hedetniemi, Roman domination in graphs, Discrete Mathmatics 278 (2004) 11-22. [3] n. Dehgardi, s. Norouzian and s. M. Sheikholeslami, bounding the domination number of a tree in terms of its annihilation number, Transactions on Combinatorics , (2013) , pp. 9-16. [4] M. Liedloff, T. Kloks, J. Liu, and S. H. Peng , Roman domination in some special classes of graphs , WG 2005, LNCS 3787 (2005) 103-114. [5] C. S. ReVelle. Can you protect the Roman Empire? Johns Hopkins Magazine 49 (1997), no. 2, 40. [6] C. S. ReVelle, and K. E. Rosing, Defenders imperium Romanum: A classical problem in military strategy, Amer. Math. Monthly 107, (2000), pp. 585–594. [7] I. Stewart, Defend the Roman Empire, Scientific American 281 (1999) 136-139. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信