Back to Search Start Over

On the crossing numbers of join products of W_{4}+P_{n} and W_{4}+C_{n}

Authors :
Juraj Valiska
Michal Staš
Source :
Opuscula Mathematica, Vol 41, Iss 1, Pp 95-112 (2021)
Publication Year :
2021
Publisher :
AGH Univeristy of Science and Technology Press, 2021.

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. The main aim of the paper is to give the crossing number of the join product \(W_4+P_n\) and \(W_4+C_n\) for the wheel \(W_4\) on five vertices, where \(P_n\) and \(C_n\) are the path and the cycle on \(n\) vertices, respectively. Yue et al. conjectured that the crossing number of \(W_m+C_n\) is equal to \(Z(m+1)Z(n)+(Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n+ \big\lceil\frac{m}{2}\big\rceil +2\), for all \(m,n \geq 3\), 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, this conjecture was proved for \(W_3+C_n\) by Klešč. We establish the validity of this conjecture for \(W_4+C_n\) and we also offer a new conjecture for the crossing number of the join product \(W_m+P_n\) for \(m\geq 3\) and \(n\geq 2\).

Details

Language :
English
ISSN :
12329274
Volume :
41
Issue :
1
Database :
OpenAIRE
Journal :
Opuscula Mathematica
Accession number :
edsair.doi.dedup.....67887cfc70365d891b58cc4d39d5a073