On the crossing number of the join of the wheel on six vertices with a path

Berežný, Štefan and Staš, Michal

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 the paper is to give the crossing number of join product W_5+P_n for the wheel W_5 on six vertices, where P_n is the path on n vertices. Staš and Valiska conjectured that the crossing number of W_m+P_n is equal to Z(m+1)Z(n) + (Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n +1, for all m\geq 3, n\geq 2, where Zarankiewicz’s number is defined as Z(n)=\big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor for n\geq 1. Recently, this conjecture was proved for W_3+P_n by Klešč and Schrötter, and for W_4+P_n by Sta\v s and Valiska. We establish the validity of this conjecture for W_5+P_n. The conjecture also holds due to some isomorphisms for W_m+P_2, W_m+P_3 by Klešč, and for W_m+P_4 by Staš for all m\geq 3.

Additional Information


  Staš, Michal, Berežný, Štefan