The crossing numbers of join products of seven graphs of order six with paths and cycles

Staš, Michal and Timková, Mária 

Full PDF


The crossing number \mathrm{cr}(G) of a graph G is the minimum number of edge crossings over all drawings of G in the plane. The main aim of this paper is to give the crossing numbers of the join products of seven graphs on six vertices with paths and cycles on n vertices. The proofs are done with the help of several well-known auxiliary statements, the idea of which is extended by a suitable classification of subgraphs that do not cross the edges of the examined graphs. Finally, for m at least three and n=5, we also establish the validity of a conjecture introduced by Sta\v s and Valiska concerning the crossings numbers of the join products of the wheels on m+1 vertices with the paths on n vertices.


Additional Information


  Staš, Michal, Timková, Mária