Crossing Numbers Of Certain Families Of Graphs

Crossing numbers of graphs are in general very difficult to compute. The exact crossing numbers of very few families of graphs are known. Using computer algorithm to compute upper bounds, and using mathmatical techniques to get lower bounds, this thesis researches on the crossing numbers of some graphs with relative large order or with relative large crossing number.The exist algorithm CCN proposed in 2002 computes the crossing numbers of all the graphs with some order. Unfortunately, the crossing number of a graph is NP complete, and not much hope is held for efficiently finding all optimal drawings-or even a single optimal drawing-for all graphs. An algorithm CCN^* is presented in the thesis to compute upper bounds of the crossing number of path power graphs P_n^k. Let p=|V(G)|. The upper bounds of crossing numbers of P_n^k where p≤12 or 13≤p≤20 with k≤9 are computed by CCN^*.Then we investigate the Crossing number of Cartesian products with cycles and paths. For the Cartesian product of cycle and complete graph, Ringeisen and Beineke have proved that cr(C₃â–¡C_n)=n and cr(K₄â–¡C_n)=3n. The thesis obtains a lower bound for K_mâ–¡C_n using a special crossing counting method for K_mâ–¡C_n, i.e. cr(K_mâ–¡C_n)≥n×cr(K_m+2) for n≥3 and m≥5. It is also proved that, cr(K_mâ–¡C_n)≤n/4(?)(m+2)/2」(?)(m+1)/2」(?)m/2」(?)(m-1)/2」for m=5, 6, 7 and for m≥5 with even n≥4, and the equality holds for m=5, 6, 7 and for m=8, 9, 10 with even n≥4.The thesis also studies the Cartesian product of path with complete graph K_m, complete bipartite graph K_m,l and cone, respectively. A special crossing counting method for the Cartesian product with paths is presented to obtain lower bounds of cr(K_mâ–¡P_n), cr(K_2,lâ–¡P_n), cr(W_mâ–¡P_n) and cr(W_2.mâ–¡P_n). And the crossing number of K₆â–¡P_n, K_2,1â–¡P_n, W_mâ–¡P_n and W_2,mâ–¡P_n are determined.Finally, we use the counting methods developed in this thesis to study other crossing number problems. As application examples, the crossing numbers of Kn(?)del graph J_3,n and Flower Snark and related graph F_n are determined.