廣義彼得森圖形的控制數; Domination in generalized Petersen graphs.

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/48277

Title:	廣義彼得森圖形的控制數;Domination in generalized Petersen graphs.
Authors:	李元馨;Yuan-shin Li
Contributors:	數學研究所
Keywords:	控制數;獨立控制數;全控制數;independent domination number;total domination number
Date:	2011-06-21
Issue Date:	2012-01-05 14:43:31 (UTC+8)
Abstract:	我們定義一個點集合的子集S 是圖G 的控制集，要滿足任一點在 V(G)-S 中至少與一個S 中的點相鄰。 G 的控制數即G 之最小控制集的元素個數，記做? (G)。S 為一個獨立控制集即S 也要是個獨立子集。 G 的獨立控制數即G 之最小獨立控制集的元素個數，記做(G) i ? 。子集 S 是圖G 的全控制集，要滿足G 中的所有點V(G)至少與一個S 中的點相鄰。G 的全控制數即G 之最小全控制集的元素個數，記做(G) t ? 。本論文是在探討在廣義Petersen 圖形中P(2k ?1,k)、P(2k,k)、 P(n,1)、P(n,2)及P(n,3)的控制數、獨立控制數及全控制數。 A vertex subset S of a graph G is a dominating set if each vertex in V(G)−S is adjacent to at least one vertex in S. The domination number of G is the cardinality of a minimum dominating set of G, denoted by γ(G). A dominating set S is called an independent dominating set if S is also an independent set. The independent domination number of G is the cardinality of a minimum independent dominating set of G, denoted by γi(G). A dominating set S is called a total dominating set if each vertex v of G is dominated by some vertex u , v of S. The total domination number of G is the cardinality of a minimum total dominating set of G, denoted by γt(G). In a generalized Petersen graph P(n, k), its vertex set should be the union of V = {v1, v2, ..., vn} and U = {u1, u2, ..., un}, and its edge set be the union of {vivi+1, viui, uiui+k} which all the subscripts are under addition modulo n and 1 ≤k ≤ ⌊n2⌋. In [3], [4], and [5], the exact values of γ(P(2k + 1, k)), γ(P(n, 1)), γ(P(n, 2)),γt(P(n, 2)), and γ(P(n, 3)) are determined. In this thesis, we will determine the exact values of γi(P(2k+1, k)), γt(P(2k+1, k)), γ(P(2k, k)), γi(P(2k, k)), and γt(P(2k, k))in Section 2. In Section 3, we find the exact values of γi(P(n, 1)), γt(P(n, 1)), and γi(P(n, 2)). We give the exact value of γi(P(n, 3)) and a lower bound and an upperbound for γt(P(n, 3)) in Section 4.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	412	View/Open

社群 sharing

Loading...