圓環弧圖上的羅馬支配問題

Abstract

圖 G 上的羅馬支配是我們為每個圖上的點分配值 0、1 或 2，並且滿足每個分配值為 0 的點需要至少一個分配值為 2 的點作為它的鄰居。羅馬支配的權重是指所有頂點賦值的總和。圖 G 如果滿足存在一組在同一個圓上的弧的集合 F，且每條在集合中的弧對應圖 G 的一個點，並且如果圖上的點 v 和點 u 有一條邊相連當且僅當它們對應的弧相交。我們稱這圖為圓環弧圖。羅馬支配問題是在所有可能的羅馬支配中找到一個權重最小的羅馬支配。在本論文中，我們希望找到一種算法來解決圓環弧圖上的羅馬支配問題。

Roman domination on a graph G is that we assign values 0, 1, or 2 to each vertex, subject to the condition that vertices whose assigned values are 0 need at least one vertex whose assigned value is 2 to be its neighbor. The weight of a Roman domination is the sum of all assigned values of the vertices. A graph G is a circular-arc graph if there exists a set F of arcs on a circle in which every arc corresponds to a vertex of G and if vertex v and vertex u have an edge if and only if their corresponding arcs are intersected. The Roman domination problem is finding a Roman domination whose weight is minimum among all possible Roman dominations. In this thesis, we want to find an algo-rithm to solve Roman domination problem on circular-arc graphs.