The Crossing Number of Join Product of kth Power of Path with Isolated Vertices and Path

Abstract

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

Date of Award	2016 Sept 5
Original language	English
Supervisor	Sun-Yuan Hsieh (Supervisor)