On the crossing numbers of join products of W 4 +P n and W 4 +C n

Opuscula Mathematica

article

Michal Staš¹  Juraj Valiska¹ 

[1] Technical University of Košice, Faculty of Electrical Engineering and Informatics, Department of Mathematics and Theoretical Informatics

关键词: graph;    crossing number;    join product;    cyclic permutation;    path;    cycle.;   

DOI  :  10.7494/OpMath.2021.41.1.95

学科分类：环境科学（综合）

来源: AGH University of Science and Technology Press

【 摘 要 】

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\).

【 授权许可】

CC BY-NC