Title: 圖的無k點子樹支配問題T_k-free Domination in Graphs Authors: 曾湄菁Mei-Jing Tzeng張鎮華Gerard J. Chang應用數學系所 Keywords: 支配;無k點子樹;樹;塊圖;domination;tree-free;tree;block graphs Issue Date: 2000 Abstract: 在一個圖G中, 每一個點都可以支配(dominate)它自己以及和它相鄰的點。對一個固定的正整數k (k>=2)而言，無k點子樹支配問題就是去找出最小的點集合，使得圖G中的每個點都可以被這個點集合支配，而這個點集合中沒有 k 點子樹圖﹝不見得一定得是延伸(induced subgraph)圖﹞存在，也就是說，每個部份(component)的大小要小於k。當k=2時，討論無k點子樹問題等於討論一般圖的獨立支配數 r_i(G)，當k>=(n+1)/2時，討論無k點子樹支配問題等於討論一般圖的支配數r(G)。在這篇論文中，我們從演算法的角度來看無k點子樹支配問題，我們使用動態規劃(dynamic programming method)設計有效率的演算法，去解決在樹(tree)和塊圖(block graphs)上的無k點子樹分配問題。The Tk-free domination number r(G;-T_k), k>=2, of a graph G is the minimum cardinality of a dominating set D such that the subgraph induced by D contains no tree of k vertices as a (not necessarily induced) subgraph; or equivalently, each component of has less than k vertices. When k=2, the T_k-free domination number is the independent domination number; when k>=(n+1)/2 , the T_k-free domination is the usual domination. In this thesis, we study T_k-free domination from an algorithmic point of view. In particular, we present efficient algorithms for the problem on trees and block graphs by the dynamic programming method. URI: http://140.113.39.130/cdrfb3/record/nctu/#NT890507022http://hdl.handle.net/11536/67703 Appears in Collections: Thesis