The crossing number of $K_{5,n}$ without one edge

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics and Theoretical Informatics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Košice, Slovak Republic

Abstract

It is conjectured that the crossing number of the complete bipartite graph $K_{m,n}$ without one edge $e$ is equal to $\big \lfloor \frac{m}{2} \big \rfloor \big \lfloor \frac{m-1}{2} \big \rfloor \big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor-\big \lfloor \frac{m-1}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor$. In this paper, we establish the validity of this conjecture for $m=5$ using combinatorial properties of cyclic permutations with proofs that can be generalized to all graphs $K_{m,n}\setminus e$ if $m$ is at least six. Further, we give a conjecture concerning crossing numbers of $K_{m,n}$ without several edges incident with a common vertex.

Keywords

Main Subjects

References

[1] O. Aichholzer, R. Fabila-Monroy, A. Fuchs, C. Hidalgo-Toscano, I. Parada, B. Vogtenhuber, and F. Zaragoza, On the 2-colored crossing number, Graph Drawing and Network Visualization (Cham) (D. Archambault and C.D. Tóth, eds.), Springer International Publishing, 2019, pp. 87–100.
[2] K. Asano, The crossing number of K1,3,n and K2,3,n, J. Graph Theory 10 (1986), no. 1, 1–8. https://doi.org/10.1002/jgt.3190100102
[3] Š. Berežný and M. Staš, Conjectures about wheels without one edge, Carpathian J. Math. 41 (2025), no. 1, 45–55. https://doi.org/10.37193/CJM.2025.01.04
[4] G.L. Chia and C.L. Lee, Crossing numbers of nearly complete graphs and nearly complete bipartite graphs, Ars Combin. 121 (2015), 437–446.
[5] R. Christian, R.B. Richter, and G. Salazar, Zarankiewicz’s conjecture is finite for each fixed m, J. Comb. Theory Ser. B 103 (2013), no. 2, 237–247. https://doi.org/10.1016/j.jctb.2012.11.001
[6] K. Clancy, M. Haythorpe, and A. Newcombe, A survey of graphs with known or bounded crossing numbers, Australas. J. Comb. 78 (2020), no. 2, 209–296.
[7] R.K. Guy, The Decline and Fall of Zarankiewicz’s Theorem, University of Calgary, Department of Mathematics, 1968.
[8] P. He, Z. Luo, and Y. Huang, Crossing number of several complete bipartite graphs by deleting one edge, J. Henan Norm. Uni. Nat. Sci. 39 (2011), no. 2, 24–26.
[9] C. Hernandez-Velez, C. Medina, and G. Salazar, The optimal drawing of $K_{5,n}$, Electron. J. Comb. 21 (2014), no. 4, 29.
[10] P.T. Ho, The crossing number of K1,1,3,n, Discrete Math. 308 (2008), no. 24, 5996–6002. https://doi.org/10.1016/j.disc.2007.11.023
[11] P.T. Ho, The crossing number of $K_{2,4,n}$, Ars Combin. 109 (2013), 527–537.
[12] Y. Huang and Y. Wang, The crossing number of K5,n+1\e, Appl. Math. Comput. 376 (2020), 125075. https://doi.org/10.1016/j.amc.2020.125075
[13] Y. Huang and T. Zhao, The crossing number of K1,4,n, Discrete Math. 308 (2008), no. 9, 1634–1638. https://doi.org/10.1016/j.disc.2006.12.002
[14] D.J. Kleitman, The crossing number of K5,n, J. Comb. Theory 9 (1970), no. 4, 315–323. https://doi.org/10.1016/S0021-9800(70)80087-4
[15] D.J. Kleitman, A note on the parity of the number of crossings of a graph, J. Comb. Theory Ser. B 21 (1976), no. 1, 88–89.
[16] M. Klešč, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Math. 310 (2010), no. 9, 1475–1481. https://doi.org/10.1016/j.disc.2009.08.018
[17] Z.D. Ouyang, J. Wang, and Y.Q. Huang, The crossing number of the Cartesian product of paths with complete graphs, Discrete Math. 328 (2014), 71–78. https://doi.org/10.1016/j.disc.2014.03.011
[18] Z.D. Ouyang, J. Wang, and Y.Q. Huang, Two recursive inequalities for crossing numbers of graphs, Front. Math.
China. 12 (2017), no. 3, 703–709. https://doi.org/10.1007/s11464-016-0618-8
[19] M. Shaefer, The graph crossing number and its variants: A survey, Electron. J. Comb. (2024), no. DynamicSurveys, DS21. https://doi.org/10.37236/2713
[20] M. Staš, On the crossing number of the join of the wheel on five vertices with the discrete graph, Bull. Aust. Math. Soc. 101 (2020), no. 3, 353–361. https://doi.org/10.1017/S0004972719001199
[21] M. Staš, Calculating crossing numbers of graphs using their redrawings, Symmetry 15 (2023), no. 1, 175. https://doi.org/10.3390/sym15010175
[22] M. Staš and M. Timková, The influence of separating cycles in drawings of $K_5 \setminus e$ in the join product with paths and cycles, Math. Slovaca 74 (2024), no. 5, 1089–1106. https://doi.org/10.1515/ms-2024-0079
[23] M. Staš and J. Valiska, On problems of CF-connected graphs for Km,n, Bull. Aust. Math. Soc. 104 (2021), no. 2, 203–210. https://doi.org/10.5614/ejgta.2023.11.2.12
[24] Z. Su, Calculating crossing numbers of graphs using combinatorial principles, Math. Probl. Eng. 2022 (2022), no. 1, 4550953. https://doi.org/10.1155/2022/4550953
[25] D.B. West, Introduction to Graph Theory, Prentice Hall:Upper Saddle River, 2011.
[26] D.R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing number conjecture, J. Graph Theory 17 (1993), no. 6, 657–671. https://doi.org/10.1002/jgt.3190170602
[27] X. Yang and Y. Wang, The conjecture on the crossing number of $K_{1,m,n}$ is true if zarankiewicz’s conjecture holds, Graphs Combin. 37 (2021), no. 3, 1083–1088. https://doi.org/10.1007/s00373-021-02303-y
[28] K. Zarankiewicz, On a problem of P. Turan concerning graphs, Fundam. Math. 41 (1955), no. 1, 137–145.
[29] W. Zheng, X. Lin, Y. Yang, and C. Cui, On the crossing number of $K_m\Box P_n$, Graphs Comb. 23 (2007), no. 3, 327–336. https://doi.org/10.1007/s00373-007-0726-z
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 01 September 2025

Files

Share

How to cite

Statistics