保距圖上的成對支配問題

Abstract

一個圖 G 的點子集合 D 如果滿足「任意不在此集合中的點皆與 D 中至少一點相鄰」，則我們稱 D 為「支配點集合」；此外，如果 D 在 G 中的衍生子圖有一個完美配對，則我們稱 D 為「成對支配點集合」。「成對支配問題」指的是在給定圖中找出最小成對支配點集合的點個數。 一個圖 G 如果滿足「任意兩點在任意包含此兩點的連通衍生子圖中的距離皆相等」，則我們稱 G 為「保距圖」。在這篇論文中，我們提出了一個時間複雜度為 O(n^2) 且實作於分解樹上的動態規劃演算法來解決保距圖上的成對支配問題，其中 n 為給定圖的點個數。 一個圖 G 如果滿足「在圖 G 的點集合與一個圓形的弦集合之間存在一個一對一對應使得圖 G 中的兩點相鄰若且唯若此兩點在圓形中對應的兩弦相交」，則我們稱 G 為「圓形圖」。在這篇論文中，我們證明了圓形圖上的成對支配問題是 NP 完全問題。

A vertex subset D of a graph G is a dominating set if every vertex not in D is adjacent to at least a vertex in D; besides, if the subgraph of G induced by D has a perfect matching, then D is a paired dominating set. The paired domination problem is to find the size of a minimum paired dominating set for the given graph. A graph G is distance-hereditary if each pair of vertices in any connected induced subgraph has the same distance as in G. In this thesis, we propose an O(n^2)-time dynamic programming algorithm that utilizes the decomposition tree to solve the paired domination problem on distance-hereditary graphs, where n is the number of vertices of the given graph. A graph G is a circle graph if there exists a one-to-one correspondence between the vertex set of G and the chord set of a circle, where two vertices of G are adjacent if and only if the corresponding chords of the circle intersect. In this thesis, we prove that the paired domination problem is NP-complete on circle graphs.