(3.238.99.243) 您好!臺灣時間:2021/05/16 22:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林承謙
研究生(外文):Cheng-ChianLin
論文名稱:路徑圖之k次方乘冪圖與獨立點及路徑圖之聯圖的交叉數研究
論文名稱(外文):The Crossing Number of Join Product of kth Power of Path with Isolated Vertices and Path
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:44
中文關鍵詞:交叉數聯圖乘冪圖圖形理論畫法路徑圖
外文關鍵詞:Crossing numberjoin productpower graphgraph theorydrawingpath
相關次數:
  • 被引用被引用: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.
中文摘要 i
Abstract ii
誌謝 iii
Contents v
List of Figures vii
List of Tables ix
1 Introduction 1
1.1 The Crossing Number Problem . . . . . . . . 1
1.1.1 The Crossing Number of Cartesian Product Graph . . . . . . . . 2
1.1.2 The Crossing Number of Join Product Graph . . . . . . . . 3
1.1.3 The Crossing Number of Power Graph . . . . . . . . 5
1.2 Preview of this Thesis . . . . . . . . 6
2 Preliminaries 7
2.1 Basic Definitions and Notations . . . . . . . . 7
2.2 Basic Properties of Crossing Number . . . . . . . . 8
3 The Crossing Number of P^k_m + D_n 10
3.1 The Crossing Number of P^m-1_m + D_n . . . . . . . . 14
3.2 The Crossing Number of P^2_m + D_n . . . . . . . . 16
3.3 The Crossing Number of P^3_m + D_n . . . . . . . . 20
3.4 The Crossing Number of P^4_6 + D_n . . . . . . . . 27
4 The Crossing Number of P^k_m + P_n 31
4.1 The Crossing Number of P^m-1_m + P_n . . . . . . . . 31
4.2 The Crossing Number of P^2_m + P_n . . . . . . . . 33
4.3 The Crossing Number of P^3_m + P_n . . . . . . . . 34
4.4 The Crossing Number of P^4_6 + P_n . . . . . . . . 36
5 Conclusions 40
Bibliography 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 Discrete
Mathematics, 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. Schrotter, 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. Schrotter, 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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
無相關點閱論文