(3.235.108.188) 您好!臺灣時間:2021/02/25 08:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:吳嘉雯
研究生(外文):Chia-Wen Wu
論文名稱:在 Harary 圖上的 二多重完全支配問題之研究
論文名稱(外文):A Study on the Double Total Domination Problem in Harary Graphs
指導教授:王弘倫張肇明張肇明引用關係
指導教授(外文):Hung-Lung WangJou-Ming Chang
學位類別:碩士
校院名稱:國立臺北商業大學
系所名稱:資訊與決策科學研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:41
中文關鍵詞:Harary 圖二多重完全支配問題
外文關鍵詞:double total domination numberHarary graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:27
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
令 G = (V, E) 為一個最小分支度至少是 2 的圖。若在圖 G 中的點集合 D 滿 足圖上的每一個點都有至少 2 個相鄰點落在 D 中,則 D 稱為二多重完全支配 集。圖 G 上的二多重完全支配數表示為 γ×2,t(G) ,是最小二多重完全支配集的元 素個數。
本論文探討 Harary 圖 H_(2m+1,2n) (其中 2m + 1 為分支度,2n 為點數) 的二 多重完全支配問題。令 2n = (2m + 1)l + r , 0<= r<= 2m,當 r = 0 或 m + 1 <= r<= 2m 時, γ×2,t(H2m+1,2n) 已知 [Kazemi,Pahlavsay,Double total domination in Harry graphs,Communications in mathematics and applications]; 本論文針對 1 <=r <= m 且 m = 1 或 2 的情形做探討。研究結果顯示當 m = 1 時, 若 n−2 是 6 的倍數,則 γ×2,t(H2m+1,2n) = 2l+1 , 否則 γ×2,t(H_(2m+1,2n)) = 2l+2; 當 m = 2 時, γ×2,t(H_(2m+1,2n)) = 2l + 2 。
Let G = (V, E) be a graph with minimum degree at least 2. A vertex subset D is a double total dominating set of G if every vertex of G is adjacent to at least two vertices in D. The double total domination number of G, denoted as γ×2,t(G), is the size of a minimum double total dominating set in G.
In this thesis, we are concerned with the double total domination number of the Harary graph H_(2m+1,2n), where 2m + 1 is the degree of each vertex and 2n is the number of vertices. Let 2n = (2m+1)l+r, where 0 <= r <= 2m. When r = 0 or m + 1 <= r <= 2m, γ×2,t(H_(2m+1,2n)) is known [Kazemi and Pahlavsay, Double total domination in Harry graphs, Communications in Mathematics and Applications]. In this thesis, we are concerned with the case where 1 <= r <= m and m ∈ {1,2}. We obtain the following results: (i) For m = 1, γ×2,t(H_(2m+1,2n)) = 2l+1 if n−2 is divisible by 6, and γ×2,t(HH_(2m+1,2n)) = 2l+2 otherwise. (ii) For m = 2, γ×2,t(H_(2m+1,2n)) = 2l+2.
Contents
摘 要-------------- I
Abstract ----------II
誌 謝------------- III
Contents---------- IV
List of Tables-------- V
List of Figures ----------VII
1 Introduction ------------1
2 Preliminaries--------- 8
3 Main Results -----------11
3.1 DoubletotaldominationinH3,2n .................... 11 3..2DoubletotaldominationinH5,2n .................... 16
4 Conclusions----------------39
References-----------------------40
References
[1] B. Chaluvaraju, V. Chaitra, Total domination polynomial of a graph, Journal of Informatics and Mathematical Sciences, vol. 6, pp. 87–92, 2014.
[2] E.J. Cockayne, R. Dawes, S.T. Hedetniemi, Total domination in graphs, Net- works, vol. 10, pp. 211–215, 1980.
[3] F. Harary, The maximum connectivity of a graph, Proceedings of the National Academy of Sciences, vol. 48, pp. 1142–1146, 1962.
[4] M.A. Henning, A.P. Kazemi, k-tuple total domination in graphs, Discrete Ap- plied Mathematics, vol. 158, pp. 1006–1011, 2010.
[5] M.A. Henning, A.P. Kazemi, k-tuple total domination in cross product of graphs, Journal of Combinatorial Optimization, vol. 24, pp. 339–346, 2012.
[6] M. Hussain, E.T.P. Baskoro, K. Ali, On super antimagic total labeling of Harary graph, Ars Combinatoria, vol. 104, pp. 225–233, 2012.
[7] A.P. Kazemi, k-tuple total domination in complementary prisms, ISRN Discrete Mathematics, vol. 2011, Article ID 681274, 2011.
[8] A.P. Kazemi, A note on the k-tuple total domination number of a graph, Tbilisi Mathematical Journal, vol. 8, no. 2, pp. 281–286, 2015.
[9] A.P. Kazemi, P. Jalilolghadr, Chromatic number of Harary graphs, Tbilisi Mathematical Journal, vol. 9, no. 1, pp. 271–278, 2016.
[10] A.P. Kazemi, B. Pahlavsay, Double total domination in Harary graphs, Com- munications in Mathematics and Applications, vol. 8, no. 1, pp. 1–6, 2017.
[11] J.M. Keil, The complexity of domination problems in circle graphs, Discrete Applied Mathematics, vol. 42, pp. 51–63, 1993.
[12] A. Khodkar, D.A. Mojdeh, A.P. Kazemi, Domination in Harary graphs, Bull. ICA, vol. 49, pp. 61–78, 2007.
[13] R.C. Laskar, J. Pfaff, S.M. Hedetniemi, S.T. Hedetniemi, On the algorithmic complexity of total domination, SIAM Journal on Algebraic Dscrete Methods, vol. 5, no. 3, pp. 420–425, 1984 .
[14] J.K. Lan, G.J. Chang, On the algorithmic complexity of k-tuple total domina- tion, Discrete Applied Mathematics, vol. 174, pp. 81–91, 2014.
[15] A.A. McRae, Generalizing NP-completeness proofs for bipartite and chordal graph, Ph.D. Thesis, Clemson University, 1994.
[16] J. Pfaff, R.C. Laskar, S.T. Hedetniemi, NP-completeness of total and connected domination and irredundance for bipartitle graphs, Technical Report 428, Clem- son University, Dept. Math. Sciences, 1983.
[17] D. Pradhan, Algorithmic aspects of k-tuple total domination in graphs, Infor- mation Processing Letters, vol. 112, pp. 816–822, 2012.
[18] T. Ramachandran, A.N. Ahmed, Dominating-x-color number of Harary graph, International Journal of Science and Research, vol. 4, no. 3, pp. 672–674, 2015.
[19] D.B. West, Introduction to Graph Theory, 2nd edition, Prentice Hall, USA (2001).
[20] S.-H. Yang, H.-L. Wang, A note on the 2-tuple total domination problem in Harary graphs, Proceedings of International Computer Symposium (ICS 2016), Dec. 15–17, Chiayi, Taiwan.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔