carpathian_2022_38_2_337_346_001

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


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


Full PDF

carpathian_2022_38_2_337_346

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

Author(s)

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

DOI

https://doi.org/10.37193/CJM.2022.02.06