淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0608202010550300
中文論文名稱 一些圖之控制數的研究
英文論文名稱 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頁
口試委員 指導教授-高金美
委員-傅恆霖
委員-潘志實
中文關鍵字 控制數  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)。整數之控制數研究。國立交通大學應用數學系研究所碩士論文。新竹市。
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2020-08-24公開。
  • 同意授權瀏覽/列印電子全文服務,於2020-08-24起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信