# 臺灣博碩士論文加值系統

(44.200.140.218) 您好！臺灣時間：2024/07/19 01:44

:::

### 詳目顯示

:

• 被引用:0
• 點閱:225
• 評分:
• 下載:16
• 書目收藏:0
 令u和v為在無向圖G中兩個不一樣的點，且為k-connected。一個在k-connected圖G中的w-container C(u,v)是從u到v的w-disjoint路徑的一個集合，且1≦w≦k。一個在圖G 中的w-container C(u,v)若它包含了在圖G 中所有的點則為一個w*-container。一個圖G若在任何兩個不一樣的點之間它都存在著一個w-container則為w*-connected。令κ(G)為圖的連通性。一個圖G若為i*-connected則為超級延伸連通，i的範圍1<=i<=κ(G)。在本研究裡，我們所要證明的是一個n維的煎餅圖Bn是超級延伸連通若且為若n≠2。
 Let u and v be any two distinct vertices of an undirected graph G, which is k-connected. For 1w k, a w-container C(u,v) of a k-connected graph G is a set of w-disjoint paths joining u and v. A w-container C(u,v) of G is a w*-container if it contains all the vertices of G. A graph G is w*-connected if there exists a w*-container between any two distinct vertices. Let κ(G) be the connectivity of G. A graph G is super spanning connected if G is i*-connected for 1iκ(G).In this thesis, we prove that the n-dimensional burnt pancake graph Bn is super spanning connected if and only if n≠2.
 Chinese Abstract iEnglish Abstract iiAcknowledgements iiiList of Figures vChapter 1: Introduction . . . . . . . . . . . . . . . . . 1Chapter 2: The Burnt Pancake Graph and its Properties . . 5Chapter 3: Basic Lemmas . . . . . . . . . . . . . . . . 11Chapter 4: Main Result . . . . . . . . . . . . . . . . . 31Chapter 5: Conclusion . . . . . . . . . . . . . . . . . 34References . . . . .. . . . . . . . . . . . . . . . . . 35Appendix . . . . . . . . . . . . . . . . . . . . . . . 38
 [1] S. Akers and B. Krishnameuthy, A group-theoretic model for symmetric interconnection networks, IEEE Transaction on Computers, 38, 555, (1989).[2] C. H. Chang, C. K. Lin, H. M. Huang, and L. H. Hsu, The super lace-ability of the hypercubes, Information Processing Letters, 92, 15–21,(2004).[3] C.H. Chang, C.K. Lin, J.M. Tan, H.M. Huang, and L.H. Hsu, 「The Super Spanning Connectivity and Super Spanning Laceability of the Enhanced Hypercubes」, The journal of supercomputing, vol. 48 pp. 66–87, (2009).[4] C.H. Chang, C.M. Sun, H.M. Huang, and L.H. Hsu, On the equitable k*-laceability of hypercubes」, Journal of Combinatorial Optimization, 14, 349–364, (2007).[5] D.S. Cohen and M. Blum, On the problem of sorting burnt pancakes. Discrete Appl. Math. 61, 105–120, (1995).[6] W.H. Gates and C.H. Papadimitriou, Bounds for sorting by prefix re-versal, Discrete Math., 27, 47–57, (1979).[7] Q.-P. Gu, S. Peng, and I.H. Sudborough, A 2-approximation algorithm for genome rearrangements by reversals and transpositions, Theoretical Computer Science, 210, 327–339, (1999).[8] P. Hall, On representation of subsets, J. Lond. Mat. Sc., 10, 26–30, (1935).[9] M.H. Heydari and I.H. Sudborough, On the diameter of the pancake network, J. Algorithms 25, 67–94, (1997),[10] H.C. Hsu, C.K. Lin, H.M. Hung, and L.H. Hsu, The spanning connectivity of the (n, k)-star graphs」, International Journal of Foundations of Computer Science, 17, 415–434, (2006).[11] L.H. Hsu and C.K. Lin, Graph Theory and Interconnection Networks, CRC Press, 2008.[12] K. Kaneko, An algorithm for node-to-set disjoint paths problem in burnt pancake graphs, IEICE Transactions on Information and Systems, E86-D(12) , 2588–2594, (2003).[13] K. Kaneko, Hamiltonian cycles and hamiltonian paths in faulty burnt pancake graphs, IEICE Transactions on Information and Systems, E90-D(4), 716–721, (2007).[14] S. S. Kao and L. H. Hsu, The globally bi-3* and the hyper bi-3* connectedness of the spider web networks, Applied Mathematics and Computation, 170, 597–610, (2005).[15] C. K. Lin, H. M. Huang, and L. H. Hsu, The super connectivity of the pancake graphs and the super laceability of the star graphs, Theoretical Computer Science 339, 257–271, (2005).[16] C.K. Lin, H.M. Huang, and L.H. Hsu, On the spanning connectivity of graphs, Discrete Mathematics, 307, 285–289, (2007).[17] C. K. Lin, H. M. Huang, J.M. Tan, and L. H. Hsu, On spanning connected graphs, On spanning connected graphs, Discrete Mathematics, 308, 1330–1333, (2008).[18] C.K. Lin, T.Y. Ho, J.M. Tan, and L.H. Hsu, Super spanning connectivity of augmented cubes, accepted by Ars Combinatorica.[19] C.K. Lin, H.M. Huang, D. F. Hsu, and L.H. Hsu, The spanning diameter of the star graph, Networks, 48, 235–249, (2006).[20] C.K. Lin, J.M. Tan, D.F. Hsu, and L.H. Hsu, On the spanning connectivity and spanning laceability of hypercube-like networks, Theoretical Computer Science, 381, 218–229, (2007).[21] K. Menger, Zur allgemeinen Kurventheorie, Fund. Math., 10, 95–115, (1927).[22] Y. H. Teng, J.M. Tan, and L. H. Hsu, The globally bi-3*-connected property of the honeycomb rectangular torus, Information Sciences, 177, 5573–5589, (2007).[23] C.H. Tsai, J.M. Tan, and L.H. Hsu, The super connected property of recursive circulant graphs, Information Processing Letters, 91, 293–298, (2004).
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 3*連接度的完整連結立方體網路結構 2 增強型金字塔網路之ω-寬直徑 3 (n,k)-星狀圖之廣義直徑 4 局部雙扭超方體之邊容錯漢彌爾頓性質 5 蝴蝶圖,遞迴式循環圖及立方體上漢米爾頓容錯性質的研究

 無相關期刊

 1 以紮根理論建構美食部落格中網路市場行家社群發展歷程之研究 2 環丙烯與環丙烯環加成產物的質譜探討 3 應用於多核心技術在高解析度影像修補 4 科學史融入理化教學對不同學習風格的國二學生之成效探討 5 探討血中維生素D3濃度與慢性腎臟病患代謝異常之關聯 6 願力化為行動—三位志工管理者之生命敘說 7 以西班牙語為外語的台灣大學生在直接說法和間接說法方面的錯誤分析 8 西文與中文之比較結構之比較 9 餐飲舞台台上台下‧幕前幕後─來自資深廚師觀點與解讀 10 網路瀏覽行為、人格特質與旅遊景點探訪意願相關性之研究 11 碳纖維與鋰離子電池負極石墨粉分散性改善之研究 12 油脂與乳化系統對防曬產品效能的影響 13 2-丙醇、四氫吡喃與2,2,4-三甲基戊烷混合物之汽液相平衡研究 14 靈芝微脂囊的製備 15 整合休眠與傳輸排程以及繞徑問題之無線感測網路MAC層架構

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室