標題: alpha-Domination of Generalized Petersen Graph
alpha-Domination of Generalized Petersen Graph
作者: 鄭伊婕
Cheng,Yi-Jie
傅恆霖
史青林
Fu,Hung-Lin
Shiue,Chin-Lin
應用數學系所
關鍵字: 控制數;α-控制數;正則圖;廣義彼德森圖;α−dominating;α−domination number;generalized Petersen graph;vertex cover number;domination number;P(n, k)
公開日期: 2013
摘要: 一個圖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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070152223
http://hdl.handle.net/11536/74594
Appears in Collections:Thesis


Files in This Item:

  1. 222301.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.