圖的無k點子樹支配問題

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 <D> induced by D contains no tree of k vertices as a (not necessarily induced) subgraph; or equivalently, each component of <D> 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.