系統識別號 | U0002-0608202010550300 |
---|---|
DOI | 10.6846/TKU.2020.00135 |
論文名稱(中文) | 一些圖之控制數的研究 |
論文名稱(英文) | A Study of the domination number of graphs |
第三語言論文名稱 | |
校院名稱 | 淡江大學 |
系所名稱(中文) | 數學學系碩士在職專班 |
系所名稱(英文) | Executive Master's program, Department of Mathematics |
外國學位學校名稱 | |
外國學位學院名稱 | |
外國學位研究所名稱 | |
學年度 | 108 |
學期 | 2 |
出版年 | 109 |
研究生(中文) | 林律淳 |
研究生(英文) | Lu-Chun Lin |
學號 | 705190139 |
學位類別 | 碩士 |
語言別 | 繁體中文 |
第二語言別 | |
口試日期 | 2020-07-04 |
論文頁數 | 26頁 |
口試委員 |
指導教授
-
高金美(cmfu@mail.tku.edu.tw)
委員 - 傅恆霖 委員 - 潘志實 |
關鍵字(中) |
控制數 k-控制數 |
關鍵字(英) |
domination number k-domination number |
第三語言關鍵字 | |
學科別分類 | |
中文摘要 |
在此論文中,我們先由已知的路徑圖與迴圈圖的控制數,去獲得兩個圖的聯集的控制數與原來各自圖的控制數的關係,即何時 γ(P_n∪P_m )=γ(P_n )+γ(P_m )?何時 γ(P_n∪C_m )=γ(P_n )+γ(C_m )? 再從圖 P_n □ P_m 控制數的探討延伸至圖 P_n □ C_m,由兩種圖的差異性得到以下結果 結果請詳見紙本與電子論文 |
英文摘要 |
In this thesis we start from the domination numbers of paths and cycles, to obtain that when can we get γ(P_n∪P_m )=γ(P_n )+γ(P_m ) and γ(P_n∪C_m )=γ(P_n )+γ(C_m ) respectively. Next, we get the relationship between the domination number of P_n □ P_m and P_n □ C_m as follows: Last part we obtain that the k-domination number of P_n □ C_m as follows Please see the thesis and electronic thesis for the results |
第三語言摘要 | |
論文目次 |
謝 辭 .......................................i 中 文 摘 要 ..................................ii 英 文 摘 要 ..................................iii 圖目錄 .......................................v 表目錄 .......................................vii 第一章 簡介 ..................................1 第二章 預備知識 ...............................3 第三章 主要結果 ...............................9 第四章 總結 ..................................25 參考書目 ......................................26 圖目錄 圖 2 1 圖 G=(V,E) 3 圖 2 2 長度為4的路徑 P_5 4 圖 2 3 長度為4的迴圈 C_4 4 圖 2 4 {a,c,d}為圖G的一個控制集 5 圖 2 5 圖 P_3□P_4 6 圖 2 6 γ_1 (P_2□C_3 ) 7 圖 2 7 γ_2 (P_2□C_3 ) 7 圖 3 1 ●為P_9控制點的位置 10 圖 3 2 ●為P_10控制點的位置 10 圖 3 3 ●為P_11控制點的位置 10 圖 3 4 P_7∪P_4 11 圖 3 5 P_4∪P_5 11 圖 3 6 P_n∪P_m 12 圖 3 7 P_n∩C_m 13 圖 3 8 P_n∪C_m 14 圖 3 9 圖P_2□P_m 19 圖 3 10 P_2□P_4 與 P_2□C_4 20 圖 3 11 P_3□P_m 20 圖 3 12 P_3□P_4 與 P_3□C_4 21 圖 3 13 P_4□P_6 與 P_4□C_6 21 圖 3 14 γ_k (P_2□C_3 ) 23 圖 3 15 γ_k (P_2□C_4 ) 24 表目錄 表 3 1 12 表 3 2 14 表 3 3 16 表 3 4 17 表 3 5 18 |
參考文獻 |
[1] B. Brešar , M.A. Henning, S. Klavžar, On integer domination in graphs and vizing-like problems, Taiwan J. Math. 10.5 (2006), 1317-1328. [2] G. Chartrand and P. Zhang, Introduction to Graph Theory, McGraw-Hill, Boston, Mass, USA, 2005. [3] G. Chen, W. Piotrowski, W. Shreve A partition approach to Vizing’s conjecture, J. Graph Theory 21(1996), 103-111. [4] W.E. Clark, S. Suen, An inequality related to Vizing's conjecture, the electronic journal of combinatorics, 7.1 (2000) Note4, 3 pp.(electronic) [5] G. Domke, S.T. Hedetniemi, R.C. Laskar, G. Fricke, Relationships between integer and fractional parameters of graphs, in: Graph Theory, Combinatorics, and Applications vol. 2, John Wiley & Sons, Inc., 1991, pp. 371-387. [6] D. Gonçalves, A. Pinlou, M. Rao, S. Thomassé, The Domination Number of Grids, SIAM J. Discrete Math., 25(3), 1443–1453. [7] X. Hou, Y. Lu, On the {k}-domination number of Cartesian products of graphs, Discrete Math. 309 (2009), 3413-3419. [8] V. G. Vizing, Some unsolved problems in graph theory. Uspehi Mat. Nauk 23 (1968) no. 6 (144), 117–134. [9] 關玉婷(2017)。整數之控制數研究。國立交通大學應用數學系研究所碩士論文。新竹市。 |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信