| 姓名 |
李元馨(Yuan-shin Li)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
廣義彼得森圖形的控制數
(Domination in generalized Petersen graphs.)
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
我們定義一個點集合的子集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.
|
| 關鍵字(中) |
★ 控制數
★ 獨立控制數
★ 全控制數 |
關鍵字(英) |
★ independent domination number
★ total domination number
★ domination number |
| 論文目次 |
Contents
Abstract (in English) ii
Contents iii
1 Introduction 1
2 Varied domination numbers of P(n, ⌊n
2
⌋) 4
3 Varied domination numbers of P(n, 1) and P(n, 2) 18
4 Varied domination numbers of P(n, 3) 30
References 41
ii
|
| 參考文獻 |
References
[1] A. Behzad, M. Behzad, and C. E. Praeger, On the domination number of the
generalized Petersen graphs, Discrete Mathematics 308(2008), 603-610.
[2] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American
Elsevier, New York, 1976.
[3] Jianxiang Cao, Weiguo Lin, and Minyong Shi, Total Domination Number of
Generalized Petersen Graphs, Intelligent Information Management 2009, 15-18
[4] B. J. Ebrahimi, N. Jahanbakht, and E. S. Mahmoodian, Vertex domination of
generalized Petersen graphs , Discrete Mathematics 309(2009), 4355-4361.
[5] H. Yan, L. Kang, and G. Xu, The exact domination number of the generalized
Petersen graphs, Discrete Mathematics 309(2009), 2596-2607.
|
| 指導教授 |
廖勝強(Sheng-Chyang Liaw)
|
審核日期 |
2011-6-21 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
