The Crossing Numbers Of Joins Of Several Special Graphs With Empty Graph As Well As Path And Cycle

Crossing number problems were introduced by Turan, who first inquire about the crossing number of the complete bipartite graph. The crossing number of a graph is the smallest number of crossings in all drawing of graph. There are only few results concerning crossing numbers of join of graphs. Crossing number problems are, in general, very difficult. It was proved by Garey and Johnson in1983that computing the crossing number of a graph is an NP-hard problem. Crossing number serves as useful models for a broad range of applications such as VLSI-Layout and computer science. Therefore, the research about crossing number as a subbranch of graph theory has been developed rapidly.This thesis is concerned with the problem of crossing number of graph. More specifically, our aim is to decide the crossing numbers of joins of graph G1,F4,G2with empty graphs as well as paths and cycles, where G1, F4, G2are given in thesis.There are four parts in this thesis. Some preliminaries are given in Chapter1. Firstly, we introduce background and progress about crossing number. Then, some notations and terminologies are introduced and defined. At last, we outline the main results of this thesis.In Chapter2, the main focus is to confirm the crossing numbers of joins of G1with empty graph, path and cycle, respectively. And we get that cr(G1∨nK1)=5[n/2][n-1/2]+n for n≥1, cr(G1∨Pn)=5[n/2][n-1/2]+n+1for n≥2and cr(G1∨Cn)=5[n/2][n-1[2]+n+3for n≥3.In Chapter3, using result on crossing number of complete bipartite, we prove the following results:the crossing number of F4V nK1is Z(5,n)+2[n/2] for n≥1and the crossing number of F4V Pn is Z(5, n)+2[n/2]+1for n≥2. In Chapter4,using Jordan carve theorem and Euler formula,we investigate the crossing number of joins of G2with empty graph,path and cycle.We prove cr(G2∨nK1)=6[n/2][n-1/2]+[n/2]for n≥1,cr(G2∨Pn)=6[n/2][n-1/2]+[n/2]+1for n≥2and cr(G2∨Cn)=6[n/2][n-1/2]+[n/2]+2for n≥3.