The crossing numbers of join products of four graphs of order five with paths and cycles

Michal Staš
Mária Timková

Abstract. 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. In the paper, we extend known results concerning crossing numbers of join products of four small graphs with paths and cycles. The crossing numbers of the join products \(G^\ast + P_n\) and \(G^\ast + C_n\) for the disconnected graph \(G^\ast\) consisting of the complete tripartite graph \(K_{1,1,2}\) and one isolated vertex are given, where \(P_n\) and \(C_n\) are the path and the cycle on \(n\) vertices, respectively. In the paper also the crossing numbers of \(H^\ast + P_n\) and \(H^\ast + C_n\) are determined, where \(H^\ast\) is isomorphic to the complete tripartite graph \(K_{1,1,3}\). Finally, by adding new edges to the graphs \(G^\ast\) and \(H^\ast\), we are able to obtain crossing numbers of join products of two other graphs \(G_1\) and \(H_1\) with paths and cycles.

Keywords: graph, crossing number, join product, path, cycle, separating cycle.

Mathematics Subject Classification: 05C10, 05C38.

Full text (pdf)