臺灣博碩士論文加值系統

在這一篇論文中，我們討論了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.

中文提要 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).