The crossing numbers of join products of $K_4\cup K_1$ with cycles

Document Type : Original paper

Authors

Department of Mathematics and Theoretical Informatics, Faculty of Electrical Engineering and Informatics, Technical University of Kosice

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. In the paper, we extend known results concerning crossing numbers of join products of two small graphs with cycles. The crossing number of the join product $G^\ast + C_n$ for the disconnected graph $G^\ast$ consisting of the complete graph $K_{4}$ and one isolated vertex is given, where $C_n$ is the cycle on $n$ vertices. The proof of the main result is done with the help of lemma whose proof is based on a special redrawing technique. Up to now, the crossing numbers of $G + C_n$ were done only for a few disconnected graphs $G$. Finally, by adding new edge to the graph $G^\ast$, we are able to obtain the crossing number of $G_1+C_n$ for one other graph $G_1$ of order five.

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.
https://doi.org/10.1007/978-3-030-35802-0 7
[2] Š. Berežný and M. Staš, On the crossing number of the join of the wheel on six vertices with a path, Carpathian J. Math. 38 (2022), no. 2, 337–346.
https://doi.org/10.37193/CJM.2022.02.06
[3] M. Chimani and T. Wiedera, An ILP-based proof system for the crossing number problem, 24th Annual European Symposium on Algorithms (ESA 2016) (Dagstuhl, Germany) (P. Sankowski and C. Zaroliagis, eds.), Leibniz Interna-
tional Proceedings in Informatics (LIPIcs), vol. 57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016, pp. 29:1–29:13
https://doi.org/10.4230/LIPIcs.ESA.2016.29
[4] 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.
[5] Z. Ding, Rotation and crossing numbers for join products, Bull. Malays. Math. Sci. Soc. 43 (2020), no. 6, 4183–4196.
https://doi.org/10.1007/s40840-020-00916-9
[6] M.R. Garey and D.S. Johnson, Crossing number is NP-complete, SIAM J. Discrete Math. 4 (1983), no. 3, 312–316.
https://doi.org/10.1137/0604033
[7] R.K. Guy, Crossing numbers of graphs, Graph Theory and Applications (Berlin, Heidelberg) (Y. Alavi, D. R. Lick, and A. T. White, eds.), Springer Berlin Heidelberg, 1972, pp. 111–124.
[8] C. Hernández-Vélez, C. Medina, and G. Salazar, The optimal drawing of $K_{5,n}$, Electron. J. Comb. 21 (2014), no. 4, Article Number: P4.1
https://doi.org/10.37236/2777
[9] D.J. Kleitman, The crossing number of $K_{5,n}$, J. Combin. Theory 9 (1970), no. 4, 315–323.
https://doi.org/10.1016/S0021-9800(70)80087-4
[10] M. Klešč, The join of graphs and crossing numbers, Electron. Notes Discrete Math. 28 (2007), 349–355.
https://doi.org/10.1016/j.endm.2007.01.049
[11] 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
[12] 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.
[13] M. Klešč, D. Kravecová, and J. Petrillová, The crossing numbers of join of special graphs, Electr. Eng. Inform. 2 (2011), 522–527.
[14] M. Klešč, J. Petrillová, and M. Valo, On the crossing numbers of cartesian products of wheels and trees, Discuss. Math. Graph Theory 37 (2017), no. 2, 399–413.
https://doi.org/10.7151/dmgt.1957
[15] M. Klešč and Š. 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.
https://doi.org/10.7151/dmgt.1548
[16] M. Klešč and Š. Schrötter, The crossing numbers of join of paths and cycles with two graphs of order five, Mathematical Modeling and Computational Science (Berlin, Heidelberg) (G. Adam, J. Buša, and M. Hnatič, eds.), Springer Berlin Heidelberg, 2012, pp. 160–167.
[17] M. Klešč and M. Staš, Cyclic permutations in determining crossing numbers, Discuss. Math. Graph Theory 42 (2022), no. 4, 1163–1183.
https://doi.org/10.7151/dmgt.2351
[18] M. Klešč and M. Valo, Minimum crossings in join of graphs with paths and cycles, Acta electrotech. inform. 12 (2012), no. 3, 32–37.
https://doi.org/10.2478/v10198-012-0028-0
[19] M. Li, The crossing numbers of the join of a 5-vertex graph with vertex, path and cycle, J. Yangzhou Uni. Nat. Sci. Ed. 18 (2015), no. 1, 4–8.
[20] R.K. Nath, B. Sen, and B.K. Sikdar, Optimal synthesis of QCA logic circuit eliminating wire-crossings, IET Circuits Devices Syst. 11 (2017), no. 3, 201–208.
https://doi.org/10.1049/iet-cds.2016.0252
[21] Z.D. Ouyang, J. Wang, and Y.Q. Huang, The crossing number of join of the generalized petersen graph $P(3, 1)$ with path and cycle, Discuss. Math. Graph Theory 38 (2018), no. 2, 351–370.
https://doi.org/10.7151/dmgt.2005
[22] M. Staš, On the crossing number of join product of the discrete graph with special graphs of order five, Electron. J. Graph Theory Appl. 8 (2020), no. 2, 339–351.
https://dx.doi.org/10.5614/ejgta.2020.8.2.10
[23] M. Staš, Parity properties of configurations, Mathematics 10 (2022), no. 12, Article ID: 1998
https://doi.org/10.3390/math10121998
[24] M. Staš and M. Švecová, The crossing numbers of join products of paths with three graphs of order five, Opuscula Math. 42 (2022), no. 4, 635–651.
http://doi.org/10.7494/OpMath.2022.42.4.635
[25] M. Staš and M. Švecová, Disconnected spanning subgraphs of paths in the join products with cycles, Art Discrete Appl. Math. 6 (2023), no. 3, #P3.06
https://doi.org/10.26493/2590-9770.1540.7b1
[26] M. Staš and M. Timková, The crossing numbers of join products of four graphs of order five with paths and cycles, Opuscula Math. 43 (2023), no. 6, 865–883.
http://doi.org/10.7494/OpMath.2023.43.6.865
[27] M. Staš and M. Timková, The crossing numbers of join products of seven graphs of order six with paths and cycles, Carpathian J. Math. 39 (2023), no. 3, 727–743.
[28] M. Staš and J. Valiska, On the crossing numbers of join products of $W_4 +P_n$ and $W_4 + C_n$, Opuscula Math. 41 (2021), no. 1, 95–112.
https://doi.org/10.7494/OpMath.2021.41.1.95
[29] Z. Su and Y. Huang, Crossing number of join of three 5-vertex graphs with $P_n$, App. Math. China 29 (2014), no. 2, 245–252.
[30] P. Turán, A note of welcome, J. Graph Theory 1 (1977), no. 1, 7–9.
[31] D.B. West, Introduction to Graph Theory, Prentice Hall, 2011.
[32] 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
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 05 April 2024

Files

Share

How to cite

Statistics