Opuscula Math. 41, no. 1 (2021), 95-112
https://doi.org/10.7494/OpMath.2021.41.1.95

Opuscula Mathematica

# On the crossing numbers of join products of W4+Pn and W4+Cn

Michal Staš
Juraj Valiska

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$$.

Keywords: graph, crossing number, join product, cyclic permutation, path, cycle.

Mathematics Subject Classification: 05C10, 05C38.

Full text (pdf)

1. Š. Berežný, J.Jr. Buša, Algorithm of the cyclic-order graph program (implementation and usage), J. Math. Model. and Geometry 7 (2019), no. 3, 1-8.
2. Š. Berežný, M. Staš, Cyclic permutations and crossing numbers of join products of two symmetric graphs of order six, Carpathian J. Math. 35 (2019), no. 2, 137-146.
3. Š. Berežný, M. Staš, On the crossing number of join of the wheel on six vertices with the discrete graph, Carpathian J. Math. 36 (2020), no. 3, 381-390.
4. K. Clancy, M. Haythorpe, A. Newcombe, A survey of graphs with known or bounded crossing numbers, Australas. J. Combin. extbf78 (2020), no. 2, 209-296.
5. E. Draženská, On the crossing number of join of graph of order six with path, Proc. CJS 2019: $$22$$th Czech-Japan Seminar on Data Analysis and Decision Making (2019), 41-48.
6. E. Draženská, Crossing numbers of join product of several graphs on 6 vertices with path using cyclic permutation, Proc. MME 2019: Proceedings of the 37th International Conference (2019), 457-463.
7. D.S. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic. Discrete Methods 4 (1983), 312-316.
8. C. Hernández-Vélez, C. Medina, G. Salazar, The optimal drawing of $$K_{5,n}$$ , Electronic Journal of Combinatorics 21 (2014), no. 4, Paper 4.1, 29 pp.
9. P.T. Ho, On the crossing number of some complete multipartite graphs, Utilitas Math.79 (2009), 125-143.
10. P.T. Ho, The crossing number of $$K_{1,m,n}$$, Discrete Math. 308 (2008), no. 24, 5996-6002.
11. D.J. Kleitman, The crossing number of $$K_{5,n}$$, J. Combinatorial Theory 9 (1970), 315-323.
12. M. Klešč, The crossing number of join of the special graph on six vertices with path and cycle , Discrete Math. 310 (2010), 1475-1481.
13. M. Klešč, The join of graphs and crossing numbers, Electron. Notes in Discrete Math. 28 (2007), 349-355.
14. M. Klešč, The crossing numbers of join of cycles with graphs of order four, Proc. Aplimat 2019: 18th Conference on Applied Mathematics (2019), 634-641.
15. M. Klešč, J. Petrillová, M. Valo, On the crossing numbers of Cartesian products of wheels and trees, Discuss. Math. Graph Theory 71 (2017), 399-413.
16. M. Klešč, Š. Schrötter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31 (2011), no. 2, 321-331.
17. M. Klešč, Š. Schrötter, The crossing numbers of join of paths and cycles with two graphs of order five, Combinatorial Algorithms, Springer, LNCS 7125 (2012), 160-167.
18. M. Klešč, M. Staš, Cyclic permutations in determining crossing numbers, Discuss. Math. Graph Theory (to appear).
19. M. Staš, On the crossing number of join of the wheel on five vertices with the discrete graph, Bull. Aust. Math. Soc. 101 (2020), no. 3, 353-361.
20. M. Staš, Determining crossing number of join of the discrete graph with two symmetric graphs of order five, Symmetry 11 (2019), no. 2, 1-9.
21. M. Staš, Join products $$K_{2,3}+C_n$$, Mathematics 8 (2020), no. 6, 1-9.
22. M. Staš, J. Petrillová, On the join products of two special graphs on five vertices with the path and the cycle, J. Math. Model. and Geometry 6 (2018), no. 2, 1-11.
23. Z. Su, Y. Huang, The crossing number of ee P_n\$, J. Math. Stud. 45 (2012), no. 3, 310-314.
24. D.R. Woodall, Cyclic-order graphs and Zarankiewicz's crossing number conjecture, J. Graph Theory 17 (1993), no. 6, 657-671.
25. W. Yue, Y. Huang, Z. Ouyang, On crossing numbers of join of $$W_4+C_n$$, Comp. Eng. Appl. 50 (2014), no. 18, 79-84.
26. K. Zarankiewicz, On a problem of P. Turan concerning graphs, Fundamenta Mathematicae 41 (1954), 137-145.
• Communicated by Andrzej Żak.
• Revised: 2020-10-30.
• Accepted: 2020-11-23.
• Published online: 2021-02-08. 