(18.204.227.34) 您好！臺灣時間：2021/05/19 07:48

### 詳目顯示:::

:
 Twitter

• 被引用:0
• 點閱:34
• 評分:
• 下載:0
• 書目收藏:0
 我們說節點集合D⊆V 是圖G = (V,E) 的二步支配子集合，指的是在節點集合V中的每個點都與至少一個D 中的節點距離剛好等於2，我們則稱集合D 為圖G的二步支配子集合。支配問題的目標是在給定的一個圖G 中，找到最小的支配子集合D。支配問題本身就是一個相當經典的問題，在過去有許多人進行詳盡的研究。但支配距離為二或以上卻有很多可以研究的空間，而且在支配距離為二以上的名詞定義有一些不同，例如像是：跳躍支配、二步支配...等，在本篇論文中，我們就針對二步支配問題去進行研究，解決在區塊圖上的二步支配問題，利用區塊圖的樹狀結構，我們修正一個時間複雜度為線性的演算法來解決區塊圖上的跳躍支配問題。並對該演算法進行延伸來解決區塊圖上的二步支配問題。
 For a graph G = (V,E), D⊆V is a dominating set of G if for every vertex v∈V ,there exists a neighbor vertex u∈D.The domination problem on G is to find a dominating set D of the minimum cardinality. The domination problem is well-studied. However, there are few research with dominating distance equal to 2 or more.Recently, some domination problems are proposed considering dominating distance equal to 2 or more, e.g., hop domination and 2-step domination.For a graph G, D⊆V is a 2-step (hop) dominating set if for every vertex v∈V (v∈V-D), there exists a vertex u∈D such that the distance between v and u is equal to 2.In this paper, we study the hop and 2-step domination problems on block graphs. We use a tree-like structure of a block graph to propose a linear algorithm to solve the hop and 2-step domination problems on block graphs.i
 第一章 Introduction 1第二章 Definitions and Previous works 3第三章 Preliminaries 7第四章 Proposed Algorithms 13第五章 Conclusion and Future Work 19
 [1] Sambhu Charan Barman, Madhumangal Pal, and Sukumar Mondal. An optimal algorithm to find minimum k-hop dominating set of interval graphs. Discrete Mathematics, Algorithms and Applications, 11(02), 2019.[2] Jr Sergio Canoy, Reynaldo Villarobe Mollejon, and John Gabriel E. Canoy. Hop dominating sets in graphs under binary operations. European Journal of Pure and Applied Mathematics, 12(4):14551463, 2019.[3] Yair Caro and Michael Henning. Simultaneous domination in graphs. Graphs and Combinatorics, 30, 01 2013.[4] Gerard J. Chang. Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Applied Mathematics, 22(1):21 34, 1988.[5] Gerard J. Chang. Algorithmic Aspects of Domination in Graphs, pages 1811 1877. Springer US, Boston, MA, 1998.[6] Gerard J. Chang, Jiaojiao Wu, and Xuding Zhu. Rainbow domination on trees. Discrete Applied Mathematics, 158(1):8 12, 2010.[7] Gary Chartrand, Frank Harary, Moazzem Hossain, and Kelly Schultz. Exact 2-step domination in graphs. Mathematica Bohemica, 120:125134, 1995.[8] Natarajan Chidambaram and S.K. Ayyaswamy. Hop domination in graphs ii. Analele Stiintice ale Universitatii Ovidius Constanta, Seria Matematica, 23:187199, 06 2015.[9] E. Cockayne, S. Goodman, and S. Hedetniemi. A linear algorithm for the domination number of a tree. Information Processing Letters, 4(2):41 44, 1975.[10] Rafael S Coelho, Phablo Moura, and YoshikoWakabayashi. The k-hop connected dominating set problem: Hardness and polyhedra. Electronic Notes in Discrete Mathematics, 50:5964, 12 2015.[11] Rafael S. Coelho, Phablo F. S. Moura, and Yoshiko Wakabayashi. The k-hop connected dominating set problem: hardness and polyhedra. Electronic Notes in Discrete Mathematics, 50:5964, 2015.[12] Rafael S. Coelho, Phablo F. S. Moura, and Yoshiko Wakabayashi. The k-hop connected dominating set problem: approximation and hardness. Journal of Combinatorial Optimization, 34(4):10601083, 2017.[13] G. Dror, A. Lev, and Y. Roditty. A note: some results in step domination of trees. Discrete Mathematics, 289(1):137 144, 2004.[14] Jochen Harant, Anja Pruchnewski, and Margit Voigt. On dominating sets and independent sets of graphs. Combinatorics, Probability and Computing, 8(6):547553, 1999.[15] T.W. Haynes, S. Hedetniemi, and P. Slater. Domination in Graphs: Volume 2: Advanced Topics. Chapman & Hall/CRC Pure and Applied Mathematics. Taylor & Francis, 1998.[16] Michael Henning and Nicolas Lichiardopol. Distance domination in graphs with given minimum and maximum degree. Journal of Combinatorial Optimization, 34, 10 2016.[17] Michael A. Henning and Nader Jafari Rad. On 2-step and hop dominating sets in graphs. Graphs and Combinatorics, 33(4):913927, 2017.[18] Patricia Hersh. On exact n-step domination. Discrete Mathematics, 205(1):235 239, 1999.[19] M. F. Jalalvand and N. J. Rad. On the complexity of k-step and k-hop dominating sets in graphs. Mathematica Montisnigri, 40:3641, 2017.[20] James K. Lan and Gerard Jennhwa Chang. On the mixed domination problem in graphs. Theoretical Computer Science, 476:84 93, 2013.[21] You Lu and Jun-Ming Xu. The p-domination number of complete multipartite graphs. Discrete Mathematics, Algorithms and Applications, 06(04):1450063, 2014.[22] Kelly Schultz. Step domination in graphs. Ars Comb., 55, 04 2000.[23] Douglas Brent West. Introduction to graph theory. Prentice Hall, Upper Saddle River, N.J., 2nd edition, 2001.[24] Ben Wieland and Anant Godbole. On the domination number of a random graph. Electron J Combin, 8, 12 2001.[25] Yancai Zhao, Zuhua Liao, and Lianying Miao. On the algorithmic complexity of edge total domination. Theoretical Computer Science, 557:28 33, 2014.[26] Yancai Zhao, Lianying Miao, and Zuhua Liao. A linear-time algorithm for 2-step domination in block graphs. Journal of Mathematical Research with Applications, Vol. 35:285290, 2015.
 電子全文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 無相關點閱論文

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室