
تعداد نشریات | 5 |
تعداد شمارهها | 117 |
تعداد مقالات | 1,391 |
تعداد مشاهده مقاله | 1,409,368 |
تعداد دریافت فایل اصل مقاله | 1,376,468 |
The crossing number of $K_{5,n}$ without one edge | ||
Communications in Combinatorics and Optimization | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 10 شهریور 1404 اصل مقاله (523.52 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2025.30549.2526 | ||
نویسندگان | ||
Michal Staš* ؛ Maria Timková | ||
Department of Mathematics and Theoretical Informatics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Košice, Slovak Republic | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
drawing؛ crossing number؛ near join product؛ cyclic permutation؛ complete bipartite graph | ||
مراجع | ||
[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 | ||
آمار تعداد مشاهده مقاله: 64 تعداد دریافت فایل اصل مقاله: 37 |