若一個圖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.

[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. Erd"os 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.