循環圖上的連通控制數

Abstract

令 G 為一圖。一個 G 的點子集 S⊆V(G) 如果是一個 G 的控制集且由 S 導出的子圖是連通的話，則 S 被稱為 G 的一個連通控制集。在所有可能的連通控制集裡取最少的控制集點數，稱為 G 的連通控制數，記為 γ_c(G)。 對於一整數 n，令 D 為 {1,2,...,⌊n/2⌋} 的子集。一個圖被稱為點數為 n 且跳集為 D 的循環圖，記作 G(n;D)，若且唯若它的點集合和邊集合分別為 V(G(n;D)) = {v_i | i ∈ {0,1,...,n-1}}，及 E(G(n;D)) = {{v_i,v_j} | |i-j|_n ∈ D, i,j ∈ {0,1,...,n-1}}，其中 |i-j|_n = min{|i-j|, n-|i-j|}。 在這篇論文中，我們將探討跳集 D 為連續整數集合的循環圖 G(n;D) 的連通控制數。我們將針對特定的點數 n 及跳集 D 給出兩種不同型式的循環圖，並試圖找出 G(n;D) 連通控制數的精確值。

Let G be a graph. A set S⊆V(G) is a connected dominating set of G if S is a dominating set of G and the subgraph induced by S is connected. The minimum size among connected dominating sets of G is the connected domination number of G, denoted by γ_c(G). For an integer n, let D be a subset of {1,2,...,⌊n/2⌋}. A circulant graph of order n with the jump set D, denoted by G(n;D), is a graph whose vertex set and edge set are, respectively, defined by V(G(n;D)) = {v_i | i ∈ {0,1,...,n-1}}, and E(G(n;D)) = {{v_i,v_j} | |i-j|_n ∈ D, i,j ∈ {0,1,...,n-1}}, where |i-j|_n = min{|i-j|, n-|i-j|}. In this thesis, we study γ_c(G(n;D)), where D is a set of consecutive integers. As a consequence, for certain D and n, we obtained the exact value of γ_c(G(n;D)).