(44.192.112.123) 您好!臺灣時間:2021/03/01 03:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃振家
研究生(外文):Jenn Jia Hwang
論文名稱:路徑和環路的支配數及束縛數
論文名稱(外文):The Domination and Bondage Numbers of Paths and Cycles
指導教授:王有禮
指導教授(外文):Y.L. Wang
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:資訊管理系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:61
中文關鍵詞:k-支配k-支配集k-支配數距離為k之束縛數格狀圖
外文關鍵詞:k-dominatek-dominating setk-domination numberdistance k-bondage numbergrid graph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:268
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:14
  • 收藏至我的研究室書目清單書目收藏:0
在一個簡單圖G=(V,E)裡,一個頂點u可以支配(dominate)自己以及另一個與之相距小於或等於k的頂點v,可稱為u k-支配v。令D為V的一個子集合,若對V中的任一點v,皆可在D中找到某一點u,使得u k-支配 v,則稱此子集合D為圖G的k-支配集(k-dominating set)。如果在圖G中所有的k-支配集裡,集合D的cardinality是最小的,則我們稱︲D︱為G的最小k-支配數(minimum k-domination number),可用γk(G)表示之。如果在圖G中減去某一個邊的子集合S,使得γk(G-S)>γk(G),則上式S的最小cardinality稱為G中距離為k的束縛數(distance k-bondage number),我們用bk(G)表示之。
本篇論文中,我們主要的研究在路徑、環路及格狀圖P2×Pn上探討支配距離為1,2,3,...,k時的最小k-支配數,以及求出它們的distance k-bondage number。

Let u and v be two vertices in a simple graph G=(V,E), where V and E are the vertex and edge, respectively, sets of G. We say that u k-dominates v if their distance is less than or equal to k. A subset D of V is called a k-dominating set of G if for every vertex v in V there exists some vertex u in D which k-dominates v. If the cardinality of D is minimum among all k-dominating sets, then is said to be the minimum k-domination number, denoted γk(G), of G. The k-bondage number of G, bk(G), is the number of edges whose removed results in γk(G-S)>γk(G), where S is the set of edges.
In this thesis, we are focus on finding the minimum k-domination number and the k-bondage number of paths, cycles and grid graphs P2×Pn .

中文摘要 Ⅰ
英文摘要 Ⅱ
誌謝 Ⅲ
目錄 Ⅳ
圖表索引 Ⅴ
第一章 緒論 1
第1-1節 研究背景 1
第1-2節 研究動機 4
第1-3節 論文架構 5
第二章 初步準備 6
第2-1節 主要定義及符號 6
第2-2節 路徑的γ1(Pn)及b1(Pn) 8
第2-3節 環路的γ1(Cn)及b1(Cn) 12
第2-4節 圖形乘積的相關結果 15
第三章 最小k-支配數和distance k-bondage number 20
第3-1節 路徑的γk(Pn)及bk(Pn) 20
第3-2節 環路的γk(Cn)及bk(Cn) 23
第3-3節 P2×Pn的最小k-支配數 26
第3-4節 P2×Pn的distance 1-bondage number 30
第3-5節 P2×Pn的distance 2-bondage number 38
第3-6節 P2×Pn的distance k-bondage number 47
第四章 總結及未來研究方向 57
參考文獻 58
作者簡介 61

[1] B.D. Acharya and H.B. Walikar, Domination Critical Graphs, National Academy Science Letters Vol.2, 1979, pp.70-72.
[2] D. Bauer, F. Harary, J. Nieminen and C.L. Suffel, Domination Alteration Sets in Graphs, Discrete Mathematics Vol.47, 1983, pp.153-161.
[3] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Prindle, Weber & Schmidt, Boston, 1979).
[4] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs (Wadsworth, Belmont, CA, 1979).
[5] R.C. Brigham, P.Z. Chinn, and R.D. Dutton, Vertex Domination-Critical Graphs, Networks Vol.18, 1988, pp.173-179.
[6] T.Y. Chang, W.E. Clark, Domination Numbers of Complete Grid Graphs, Department of Mathematics, University of South Florida, 1995.
[7] V. Chvatal and W. Cook, The Discipline Number of a Graph, Discrete Mathematics Vol.86, 1990, pp.191-198.
[8] B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit Disk Graphs, Discrete Mathematics Vol.86, 1990, pp.165-177.
[9] E.J. Cockayne and S.T. Hedetniemi, Towards a Theory of Domination in Graphs, Networks Vol.7, 1977, pp.247-261.
[10] E.J. Cockayne, Domination in Undirected Graphs — a Survey, in: Y. Alavi and D.R. Lick, eds, Theory and Applications of Graphs in America’s Bicentennial Year (Springer-Verlag, Berlin, 1978).
[11] E.J. Cockayne, E. O. Hare, S.T. Hedetniemi, T.V. Wimer, Bounds for the Domination Number of Grid Graphs, Congressus Numerantium Vol.47, 1985, pp.217-228.
[12] G.S. Domke, S.T. Hedetniemi and R.C. Laskar, Fractional Packings, Coverings and Irredundance in Graphs, Congressus Numerantium Vol.66, 1988, pp.227-238.
[13] G.S. Domke, R.C. Laskar, The Bondage and Reinforcement Numbers of γf for Some Graphs, Discrete Mathematics Vol.167/168, 1997, pp.249-259.
[14] R.D. Dutton, and R.C. Brigham, An Extremal Problem for Edge Domination Insensitive Graphs, Discrete Applied Mathematics Vol.20, 1988, pp.113-125.
[15] M. Farber, Domination, Independent Domination and Duality Chordal Graphs, Discrete Applied Mathematics Vol.7, 1986, pp.115-130.
[16] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The Bondage Number of a Graph, Discrete Mathematics Vol.86, 1990, pp.47-57.
[17] G. Gunther, B. Hartnell, and D.F. Rall, Graphs whose Vertex Independence Number is Unaffected by Single Edge Addition or Deletion (submitted for publication).
[18] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969).
[19] E. O. Hare, Algorithms for Grid and Grid-like Graphs, Ph.D. Thesis, Department of Computer Science, Clemson University, 1989.
[20] E. O. Hare, S.T. Hedetniemi, W.R. Hare, Algorithms for Computing the Domination number of k×n Complete Grid Graphs, Congressus Numerantium Vol.55, 1986, pp.81-92.
[21] B.L. Hartnell, L.K. Jorgensen, P.D. Vestergaard, C.A. Whitehead, Edge Stability of the k-domination Number of Trees, Bull. ICA Vol.22, 1998, pp.31-40.
[22] B.L. Hartnell and D.F. Rall, A Characterization of Trees in which no Edge is Essential to the Domination Number, Ars Combinatoria Vol.33, 1992, pp.65-76.
[23] B.L. Hartnell and D.F. Rall, A Bound on the Size of a Graph with given Order and Bondage Number, Discrete Mathematics Vol.197/198, 1999, pp.409-413.
[24] B.L. Hartnell and D.F. Rall, Bounds on the Bondage Number of a Graph, Discrete Mathematics Vol.128, 1994, pp.173-177.
[25] T.W. Haynes, L.M. Lawson, R.C. Brigham, and R.D. Dutton, Changing and Unchanging of the Graphical Invariants: Minimum and Maximum Degree, Maximum Clique Size, Node Independence Number and Edge Independence Number, Congressus Numerantium Vol.72, 1990, pp.239-252.
[26] S.M. Hedetniemi, S.T. Hedetniemi and T.V. Wimer, Linear Time Resource Allocation Algorithms for Trees, Technic Report URI-014, Department Mathematics Science, Clemson University, 1987.
[27] S.T. Hedetniemi and R.C. Laskar, Topics on Domination, Discrete Mathematics Vol.86, 1990, pp.1-3.
[28] M.S. Jacobson and L.F. Kinch, On the Domination Number of Products of Graphs: I, Ars Combinatoria Vol.18, 1983, pp.33-44.
[29] J. Kok and C.M. Mynhardt, Reinforcement in Graphs Congressus Numerantium Vol.79, 1990, pp.225-231.
[30] A. Meir and J.W. Moon, Relations between Packing and Covering Numbers of a Tree, Pacific J. Mathematics Vol.61, 1975, pp.225-233.
[31] T.H. Rice, R.C. Brigham, and R.D. Dutton, Extremal 2-2-insensitive Graphs, Congressus Numerantium Vol.67, 1988, pp.158-166.
[32] F.S. Roberts, Graph Theory and Its Applications to Problems of Society (SIAM, Philadelphia, PA, 1978).
[33] L.A. Sanchis, Maximum Number of Edges in Connected Graphs with a Given Domination Number, Discrete Mathematics Vol.87, 1991, pp.65-72.
[34] D.P. Sumner and P. Blitch, Domination Critical Graphs, J. Combination Theory Series B Vol.34, 1983, pp.65-76.
[35] U. Teschner, A Counterexample to a Conjecture on the Bondage Number of a Graph, Discrete Mathematics Vol.122, 1993, pp.393-395.
[36] U. Teschner, A New Upper Bound for the Bondage Number of Graphs with Small Domination Number, Australasia J. Combination Vol.12, 1995, pp.27-35.
[37] U. Teschner, The Bondage Number of a Graph G can be much than Δ(G), Ars Combinatoria Vol.43, 1996, pp.81-87.
[38] U. Teschner, New Result about the Bondage Number of a Graph, Discrete Mathematics Vol.171, 1997, pp.249-259.
[39] Y.L. Wang, On the Bondage Number of a Graph, Discrete Mathematics Vol.159, 1996, pp.291-294.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔