carpathian_2020_36_3_381_390_001

On the crossing number of join of the wheel on six vertices with the discrete graph


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


Abstract

carpathian_2020_36_3_381_390_abstract

Full PDF

carpathian_2020_36_3_381_390

 

The main aim of the paper is to give the crossing number of join product W_5+D_n for the wheel W_5 on six vertices, and D_n consisting of n isolated vertices. In the proofs, it will be extend the idea of the minimum numbers of crossings between two different subgraphs from the family of subgraphs which do not cross the edges of the graph W_5 onto the family of subgraphs that cross the edges of W_5 at least twice. Further, we give a conjecture that the crossing number of W_m+D_n is equal to Z(m+1)Z(n) + (Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n for m at least three, and where the Zarankiewicz’s number Z(n)=\big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor is defined for n\geq 1. Recently, our conjecture was proved for the graphs W_m+D_n, for any n=3,4,5, by Klešč et al., and also for W_3+D_n and W_4+D_n due to the result by Klešč, Schr\”otter and by Staš, respectively. Clearly, the main result of the paper confirms the validity of this conjecture for the graph W_5+D_n.

 

 

 

 

Additional Information

Author(s)

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