alpha-Domination of Generalized Petersen Graph

Abstract

一個圖G的控制數是圖論中最重要的一個不變量，在很多文獻中都有相當不錯的研究成果。但是，控制的概念可做更進一步的探討，而α-控制數的研究就是其中的一種延伸研究。對於任意α大於0且小或等於1時，存在一集合S包含於點集合V中，如果對於所有在點集合V中卻不屬於S中的點v，點v在S中的鄰居數大或等於點v的鄰居數乘上α倍，我們就稱S是α-控制集並表示成 γα(G)。 因為我們已知對於度數為3的正則圖，當α大於0且小或等於1/3時，γα(G) = γ(G);而當α大於2/3且小或等於1時，γα(G) = γ0(G);所以在此篇論文中，我們討論在1/3 < α ≤ 2/3時，廣義彼德森圖的α-控制數，並獲得一些具體成果。

Let G = (V,E) be a graph with n vertices, m edges and no isolated vertices. For some α with 0 < α ≤ 1 and a set S ⊆ V, we say that S is α−dominating if for all v ∈ V − S, |N(v)∩ S| ≥ α|N(v)|. The size of a smallest such S is called the α−domination number of G denoted by γα(G). For positive integers n and k, the generalized Petersen graph P(n, k) is the graph with vertex set V = {u0, u1, . . ., un−1}∪{v0, v1, . . ., vn−1} and the edge set E = {uiui+1, uivi, vivi+k | i ∈ Zn} where addition is modulo n. Clearly, P(n, k) is a 3-regular graph. In this thesis, we study γα(P(n, k)). Since for 3-regular graphs γα(G) = γ(G)(domination number of G), provided 0 < α ≤ 1/3 and γα(G) = α0(G)(vertex cover number of G) provided 2/3 < α ≤ 1, we shall focus on the case 1/3 < α ≤ 2/3. As a consequence, the exact values of γα(P(n, k)) are obtained for certain n and k.