循環圖的獨立數

Abstract

令 G = (V,E) 是一個點集 V 和邊集 E 的簡單圖。獨立集 I 是一個點的子集，而且 I 中的任兩個點在 G 中不相連；最大獨立集是一個點數最多的獨立集，而這個量稱為是 G 的獨立數，記做 α(G)。 給定 n ≥ 1 和一個集合 S ⊆ {1,2,··· ,⌊n/2⌋}，一個點數 n、生成集 S 的循環圖 C_{n,S} 是一個以 V = Z_n 作為點集的圖，而且 點集 V 中任兩個點 i 和 j (i > j) 在 C_{n,S} 中有邊相連若且唯若 min{i−j,n−i + j}∈ S。 要找一個圖的獨立數是 NP-困難的，即使是平面圖也是。因此，這些年來關於獨立數的研究都專注在特定的圖上，此篇論文也不例外；我們關注的圖是循環圖，主要動機是來自於它在通訊上的應用。 我們的研究結果主要是得到 α(C_{n,S}) 的上、下界，其中 S 是一個 由連續整數構成的集合。再者，對於某些特定的 n 和 S，我們利用鴿 籠原理求得 α(C_{n,S})。

Let G = (V,E) be a simple graph. An independent set I is a vertex subset of V such that no two vertices in I are adjacent in G. A maximum independent set is an independent set with the largest cardinality, this cardinality is known as the independence number of G, denoted by α(G). Given n ≥ 1 and a set S ⊆ {1,2,··· ,⌊n/2⌋}, the circulant graph C_{n,S} of order n with generating set S is a graph whose vertex set is V = Z_n and for i,j ∈ V with i > j, {i,j} is an edge of C_{n,S} if and only if min{i−j,n−i + j}∈ S. Finding the independence number of a general graph, even a planar graph, is known to be NP-hard. Therefore, the study of this parameter focuses on special graphs over the years, this thesis is of no exception. Motivated by its applications on communications, we focus on the class of circulant graphs. As a consequence of study, we are able to derive bounds of α(C_{n,S}) mainly when S is a set of consecutive integers. Furthermore, with the application of Pigeon-hole Principle, we obtain several exact values of α(C_{n,S}), i.e., for some special n and respectively S, we have the answer of α(C_{n,S}).