(3.238.99.243) 您好！臺灣時間：2021/05/16 22:55

詳目顯示:::

:

• 被引用:0
• 點閱:53
• 評分:
• 下載:0
• 書目收藏:0
 若一個圖G中的兩條邊具有共同的內點，則稱此圖G存在一個交叉數。圖G的最小交叉數記作cr(G)。交叉數問題是在尋找一個圖中最小交叉數的解，且此問題可應用於電路佈局。雖然至今已有許多文獻探討各種聯圖的交叉數，但是關於結合乘冪圖與路徑圖之聯圖的交叉數仍無人研究。令P_m與P_n分別為m及n個頂點的路徑圖，且D_n為n個獨立點組成的圖。在本論文中，我們研究路徑圖之k次方乘冪圖與獨立點及路徑圖之聯圖的交叉數。我們證明了在m ≤ 6, n ≥ 1的條件下，路徑圖P_m之k次方乘冪圖與獨立點D_n之聯圖的交叉數，以及在m ≤ 6, n ≥ 2的條件下，路徑圖P_m之k次方乘冪圖與路徑圖P_n之聯圖的交叉數。我們發現當3 ≤ m ≤ 6, n ≥ 2時，cr(P_m^(m-1)+P_n)=cr(P_m^(m-2)+P_n)+1；當4 ≤ m ≤ 6, n ≥ 2時，cr(P_m^2+P_n)=⌊m/2⌋⌊(m-1)/2⌋⌊n/2⌋⌊(n-1)/2⌋+⌊((m-2)n)/2⌋；當5 ≤ m ≤ 6, n ≥ 2時，cr(P_m^3+P_n)=⌊m/2⌋⌊(m-1)/2⌋⌊n/2⌋⌊(n-1)/2⌋+(m-4)(2n+⌊n/2⌋-1)+4；以及當n ≥ 2時，cr(P_6^4+P_n)=6⌊n/2⌋⌊(n-1)/2⌋+6n+5。
 A graph G is said to have a crossing if two edges of G share an interior point. The minimum crossing number of G is denoted by cr(G). The crossing number problem is to find the minimum crossing solution of a graph, and it can be used in applications of circuit layout. Although the crossing numbers of join product graphs have been extensively studied, the crossing number of join product of power graphs with path is relatively unexplored. Let P_m and P_n be paths with m and n vertices, and D_n be a graph consisting of n isolated vertices. In this thesis, we investigate the crossing number of kth power of path P_m that joins with isolated vertices D_n and path P_n. We have proved the minimum crossing numbers of P_m^k+D_n for m ≤ 6, n ≥ 1, and P_m^k+P_n for m ≤ 6, n ≥ 2. We found that cr(P_m^(m-1)+P_n)=cr(P_m^(m-2)+P_n)+1 for 3 ≤ m ≤ 6, n ≥ 2; cr(P_m^2 + P_n)=⌊m/2⌋⌊(m-1)/2⌋⌊n/2⌋⌊(n-1)/2⌋+⌊((m-2)n)/2⌋ for 4 ≤ m ≤ 6, n ≥ 2; cr(P_m^3+P_n)=⌊m/2⌋⌊(m-1)/2⌋⌊n/2⌋⌊(n-1)/2⌋+(m-4)(2n+⌊n/2⌋-1)+4 for 5 ≤ m ≤ 6, n ≥ 2; and cr(P_6^4+P_n)=6⌊n/2⌋⌊(n-1)/2⌋+6n+5 for n ≥ 2.
 中文摘要 iAbstract ii誌謝 iiiContents vList of Figures viiList of Tables ix1 Introduction 11.1 The Crossing Number Problem . . . . . . . . 11.1.1 The Crossing Number of Cartesian Product Graph . . . . . . . . 21.1.2 The Crossing Number of Join Product Graph . . . . . . . . 31.1.3 The Crossing Number of Power Graph . . . . . . . . 51.2 Preview of this Thesis . . . . . . . . 62 Preliminaries 72.1 Basic Definitions and Notations . . . . . . . . 72.2 Basic Properties of Crossing Number . . . . . . . . 83 The Crossing Number of P^k_m + D_n 103.1 The Crossing Number of P^m-1_m + D_n . . . . . . . . 143.2 The Crossing Number of P^2_m + D_n . . . . . . . . 163.3 The Crossing Number of P^3_m + D_n . . . . . . . . 203.4 The Crossing Number of P^4_6 + D_n . . . . . . . . 274 The Crossing Number of P^k_m + P_n 314.1 The Crossing Number of P^m-1_m + P_n . . . . . . . . 314.2 The Crossing Number of P^2_m + P_n . . . . . . . . 334.3 The Crossing Number of P^3_m + P_n . . . . . . . . 344.4 The Crossing Number of P^4_6 + P_n . . . . . . . . 365 Conclusions 40Bibliography 42
 [1]L. W. Beineke and R. D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, Journal of Graph Theory, 4(2): 145-155, 1980.[2]P. Erdos and R. K. Guy, Crossing number problems, The American Mathematical Monthly, 80(1): 52-58, 1973.[3]M. R. Garey and D. S. Johnson, Crossing number is NP-complete, SIAM Journal on Algebraic Discrete Methods, 4(3): 312-316, 1983.[4]R. K. Guy, The Decline and Fall of Zarankiewicz's Theorem, Methods of Proof in Graph Theory (Proc. Ann Arbor Conference 1968), Academic Press, New York, 1969.[5]D. J. Kleitman, The crossing number of K_5,n, Journal of Combinatorial Theory, 9(4): 315-323, 1970.[6]M. Klesc, The crossing number of K_5 X P_n, Tatra Mountains Mathematical Publications, 18(4): 63-68, 1999.[7]M. Klesc, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Mathematics, 233(1): 353-359, 2001.[8]M. Klesc, The join of graphs and crossing numbers, Electronic Notes in DiscreteMathematics, 28: 349-355, 2007.[9]M. Klesc and D. Kravecova, The crossing number of P^2_5 X C_n, Creative Mathematics and Informatics, 17(3): 431-438, 2008.[10]M. Klesc, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Mathematics, 310(9): 1475-1481, 2010.[11]M. Klesc and S. Schrotter, The crossing numbers of join products of paths with graphs of order four, Discussiones Mathematicae Graph Theory, 31(2): 321-331, 2011.[12]M. Klesc and S. Schrotter, The crossing numbers of join of paths and cycles with two graphs of order five, in Mathematical Modeling and Computational Science, Springer Berlin Heidelberg, pp. 160-167, 2012.[13]M. Klesc and D. Kravecov a, The crossing number of P^2_n X C_3, Discrete Mathematics, 312(14): 2096-2101, 2012.[14]D. Kravecova and J. Petrillova, The crossing number of P^2_n X C_4, Acta Electrotechnica et Informatica, 12(3): 42-46, 2012.[15]F. T. Leighton, New lower bound techniques for VLSI, in Proceeding of 22nd Annual IEEE Symposium on Foundations of Computer Science, pp. 1-12, 1984.[16]Z. D. Ouyang, J. Wang, and Y. Q. Huang, The crossing number of the Cartesian product of paths with complete graphs, Discrete Mathematics, 328: 71-78, 2014.[17]H. P. Patil and D. Krishnamurthy, On power graphs with crossing number one, Discussiones Mathematicae Graph Theory, 12: 27-37, 1992.[18]F. W. Sinden, Topology of thin film circuits, Bell System Technical Journal, 45(9): 1639-1666, 1966.[19]D. B. West, Introduction to graph theory, Prentice Hall, NJ, 2 edition, 2001.[20]K. Zarankiewicz, On a problem of P. Tur an concerning graphs, Fundamenta Mathematicae, 41(1): 137-145, 1954.[21]W. P. Zheng, X. H. Lin, Y. S. Yang, and C. Cui, On the crossing number of K_m X P_n, Graphs and Combinatorics, 23(3): 327-336, 2007.[22]W. P. Zheng, X. H. Lin, Y. S. Yang, and G. Yang, On the crossing numbers of the k-th power of P_n, Ars Combinatoria, 92: 397-409, 2009.
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 路徑圖上權重備份雙中心問題

 無相關期刊

 無相關點閱論文

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