| 姓名 |
羅勝鴻(Sheng-Hung Lo)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
(Global defensive alliances in double-loop networks)
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
在這一篇論文中，我們討論了global defensive alliance number 在 double-loop networks 裡的值，但是並沒有討論全部，在裡面我們只有討論一些特殊的形式，而那些形式分別是DL(n;1,2),DL(n;1,3),DL(n;1,n/2) ,DL(3n;1,3k)。
最後，我們還用矩陣來討論global defensive alliance number ， 他可以用來檢查一個點集合 S 是否為 global defensive alliance ， 也可以利用線性規劃來把求 global defensive alliance number 的問題轉換成線性規劃求最小值的問題。 |
| 摘要(英) |
A defensive alliance in graph G = (V,E) is a set of vertices S in V satisfying
|N[v]∩S| ≧ |N(v) ∩ (V - S)| for any v in S, N(v) = {u : uv in E}, and N[v] =N(v)∪{v}. Because of such an alliance, the vertices in S, agreeing to mutually
support each other, have the strength of numbers to be able to defend themselves
from the vertices in V - S. A defensive alliance S is called global if N[S] = V .
A double-loop network DL(n; a , b) can be viewed as a directed graph with n
vertices 0,1,2,...,(n,1) and 2n directed edges of the form i -> i+a (mod n) and
i -> i+b (mod n), referred to as a-links and b-links. In this thesis, any reference to
DL(n; a, b) will mean an underlying graph of a directed graph DL(n; a , b).
In this thesis, we study global defensive alliance in DL(n; a, b). We deter-
mine the value of the global defensive alliance number in DL(n; 1, 2), DL(n; 1, 3),
DL(3n; 1, 3k), and DL(n; 1, n/2). Finally, we research into the relation between
γa(G) and integer programming for G being a k-regular graph. |
| 關鍵字(中) |
|
關鍵字(英) |
★ double-loop network
★ global alliance |
| 論文目次 |
中文提要 i
Abstract(in English) ii
誌謝 iii
Contents iv
1 Introduction 1
2 The global alliance number of DL(n;1,2) 6
3 γa(DL(n;1,3)) & γa(DL(3n;1,3k)) 9
4 The global alliance number of DL(n;1,n/2) 13
5 Futher research with integer programming 16
References 18 |
| 參考文獻 |
[1] F. Boesch and R. Tindell, Circulants and their connectivities, J. Graph Theory
8 (1984), 487-499.
[2] A. Cami, H. Balakrishnan, N. Deo, and R. D. Dutton, On the complexity of
¯nding optimal global alliances, Journal of Combinatorial Mathematics and
Combinatorial Computing 58 (2006), 23-31.
[3] G. Chartrand and L. Lesniak, Graphs & Digraphs: Third Edition, Chapman &
Hall, London (1996).
[4] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, Global defensive alliances
in graphs, Electron. J. Combin. 10 (2003), Research Paper 47, 13 pp.
[5] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination
in Graphs Marcel Dekker, NY (1998).
[6] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in Graphs:
Advanced Topices, Marcel Dekker, NY (1998).
[7] S. M. Hedetniemi, S. T. Hedetniemi, and P. Kristiansen, Alliances in graphs,
Journal of Combinatorial Mathematics and Combinatorial Computing 48
(2004), 157-177.
[8] F. k. Hwang, A complementary survey on Double-Loop Network, Theoretical
Computer Science 263 (2001), 211-229.
[9] F. K. Hwang, P. E. Wright, and X. D. Hu, Exact Reliabilities of Most Reliable
Double-Loop Networks, Networks 30 (1997), 81-90.
[10] J. S. Lee, J. K. Lan, and C. Y. Chen, On Degenerate Double-Loop L-shapes,
Journal of Interconnection Networks 7 (2006), 195-215.
[11] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ (2001). |
| 指導教授 |
廖勝強(Sheng-Chyang Liaw)
|
審核日期 |
2008-7-16 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
