The crossing numbers of join products of four graphs of order five with paths and cycles

• Autorzy: Staš Michal , Timková Mária

Identyfikatory

DOI

10.7494/OpMath.2023.43.6.865

• Języki publikacji: EN

Abstrakty

EN

The crossing number 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 four small graphs with paths and cycles. The crossing numbers of the join products G∗ + Pn and G∗ + Cn for the disconnected graph G∗ consisting of the complete tripartite graph K1,1,2 and one isolated vertex are given, where Pn and Cn are the path and the cycle on n vertices, respectively. In the paper also the crossing numbers of H∗ + Pn and H∗ + Cn are determined, where H∗ is isomorphic to the complete tripartite graph K1,1,3. Finally, by adding new edges to the graphs G∗ and H∗, we are able to obtain crossing numbers of join products of two other graphs G1 and H1 with paths and cycles.

Słowa kluczowe

EN

graph; crossing number; join product; path; cycle; separating cycle

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 6
• Strony: 865--883
• Opis fizyczny: Bibliogr. 37 poz., tab.

Twórcy

autor

Staš Michal

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

• https://orcid.org/0000-0002-2837-8879

autor

Timková Mária

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

• https://orcid.org/0000-0001-5499-9399

Bibliografia

• [1] O. Aichholzer, R. Fabila-Monroy, A. Fuchs, C. Hidalgo-Toscano, I. Parada, B. Vogtenhuber, F. Zaragoza, On the 2-colored crossing number, [in:] Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization, Lecture Notes in Computer Science (2019), 87–100.
• [2] Š. Berežný, 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.
• [3] Š. Berežný, M. Staš, On the crossing numbers of the join products of five graphs on six vertices with discrete graphs, Carpathian J. Math. 39 (2023), no. 2, 371–382.
• [4] K. Clancy, M. Haythorpe, A. Newcombe, A survey of graphs with known or bounded crossing numbers, Australasian J. Combin. 78 (2020), no. 2, 209–296.
• [5] M. Chimani, T. Wiedera, An ILP-based proof system for the crossing number problem, 24th Proceedings of the Annual European Symposium on Algorithms (2016), 1–13.
• [6] E. Draženská, On the crossing number of join of graph of order six with path, Proc. CJS 2019: 22th Czech-Japan Seminar on Data Analysis and Decision Making (2019), 41–48.
• [7] 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.
• [8] G. Fridman, Y. Vasiliev, V. Puhkalo, V. Ryzhov, A mixed-integer program for drawing orthogonal hyperedges in a hierarchical hypergraph, Mathematics 10 (2022), no. 5, 689.
• [9] M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic. Discrete Methods 4 (1983), no. 3, 312–316.
• [10] E. Gethner, L. Hogben, B. Lidicky, F. Pfender, A. Ruiz, M. Young, On crossing numbers of complete tripartite and balanced complete multipartite graphs, J. Graph Theory 84 (2017), no. 4, 552–565.
• [11] C. Hernández-Vélez, C. Medina, G. Salazar, The optimal drawing of K5,n, Electronic Journal of Combinatorics 21 (2014), no. 4, Paper 4.1, 29 pp.
• [12] P.T. Ho, The crossing number of K1,1,3,n, Ars Combinatoria 99 (2011), 461–471.
• [13] D.J. Kleitman, The crossing number of K5,n, J. Combinatorial Theory 9 (1970), no. 4, 315–323.
• [14] M. Klešč, The crossing number of join of the special graph on six vertices with path and cycle, Discrete Math. 310 (2010), no. 9, 1475–1481.
• [15] M. Klešč, The join of graphs and crossing numbers, Electron. Notes in Discrete Math. 28 (2007), 349–355.
• [16] 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.
• [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šč, Š. 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.
• [19] M. Klešč, M. Staš, Cyclic permutations in determining crossing numbers, Discuss. Math. Graph Theory 42 (2022), no. 4, 1163–1183.
• [20] M. Klešč, M. Valo, Minimum crossings in join of graphs with paths and cycles, Acta Electrotechnica et Informatica 12 (2012), no. 3, 32–37.
• [21] M. Klešč, D. Kravecová, J. Petrillová, The crossing numbers of join of special graphs, Electrical Engineering and Informatics 2: Proceeding of the Faculty of Electrical Engineering and Informatics of the Technical University of Košice (2011), 522–527.
• [22] M. Klešč, D. Kravecová, J. Petrillová, On the crossing numbers of Cartesian products of paths with special graphs, Carpathian J. Math. 30 (2014), no. 3, 317–325.
• [23] M. Klešč, J. Petrillová, M. Valo, Minimal number of crossings in strong product of paths, Carpathian J. Math. 29 (2013), no. 1, 27–32.
• [24] M. Klešč, J. Petrillová, M. Valo, On the crossing numbers of Cartesian products of wheels and trees, Discuss. Math. Graph Theory 37 (2017), no. 2, 399–413.
• [25] M. Klešč, M. Staš, J. Petrillová, The crossing numbers of join of special disconnected graph on five vertices with discrete graphs, Graphs and Combinatorics 38 (2022), no. 2, Article no. 35.
• [26] R.K. Nath, B. Sen, B.K. Sikdar, Optimal synthesis of QCA logic circuit eliminating wire-crossings, IET Circuits, Devices and Systems 11 (2017), no. 3, 201–208.
• [27] Z. Ouyang, J. Wang, Y. 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.
• [28] M. Schaefer, The graph crossing number and its variants: A survey, The Electronic Journal of Combinatorics (2013), #DS21.
• [29] M. Staš, Alternative proof on the crossing number of K1,1,3,n, Acta Electrotechnica et Informatica 19 (2019), no. 1, 19–24.
• [30] M. Staš, The crossing numbers of join products of paths and cycles with four graphs of order five, Mathematics 2021, 9(11), 1277.
• [31] M. Staš, On the crossing numbers of the join products of six graphs of order six with paths and cycles, Symmetry 2021, 13(12), 2441.
• [32] M. Staš, Parity properties of configurations, Mathematics 2022, 10(12), 1998.
• [33] 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.
• [34] M. Staš, M. Švecová, The crossing numbers of join products of paths with three graphs of order five, Opuscula Math. 42 (2022), no. 4, 635–651.
• [35] M. Staš, J. Valiska, On the crossing numbers of join products of W4 + Pn and W4 + Cn, Opuscula Math. 41 (2021), no. 1, 95–112.
• [36] Z. Su, Y. Huang, Crossing number of join of three 5-vertex graphs with Pn, App. Math. China 29 (2014), no. 2, 245–252.
• [37] D.R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing number conjecture, J. Graph Theory 17 (1993), no. 6, 657–671.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)