Determining crossing numbers of two specific graphs of order six using cyclic permutations

Michal Staš


The main aim of the paper is to give the crossing number of join product $G+D_n$ for the connected graph $G$ of order six consisting of $P_4+D_4$ and of one leaf incident with some inner vertex of the path $P_4$ on four vertices, and $D_n$ consists on $n$ isolated vertices. In the proofs,  it will be extend the idea of the minimum numbers of crossings between two different subgraphs from the set of subgraphs which do not cross the edges of the graph $G$ onto the set of subgraphs which cross the edges of $G$ exactly once. Due to the mentioned algebraic topological approach, we are able to  extend known results concerning crossing numbers for join products of new graphs. The proofs are also done with the~help of software that generates all cyclic permutations for a given number $k$, and creates a~new graph $\hbox{COG}$ for calculating the distances between all $(k-1)!$ vertices of the graph.  Finally, by adding one edge to the graph $G$, we are able to obtain the crossing number of the join product with the discrete graph $D_n$ for one other graph.


  • There are currently no refbacks.