The crossing numbers of join products of paths with three graphs of order five

• Autorzy: Staš Michal , Švecová Mária

Identyfikatory

DOI

10.7494/OpMath.2022.42.4.635

• Języki publikacji: EN

Abstrakty

EN

The main aim of this paper is to give the crossing number of the join product G∗ + Pn for the disconnected graph G∗ of order five consisting of the complete graph K4 and one isolated vertex, where Pn is the path on n vertices. The proofs are done with the help of a lot of well-known exact values for the crossing numbers of the join products of subgraphs of the graph G∗ with the paths. Finally, by adding new edges to the graph G∗, we are able to obtain the crossing numbers of the join products of two other graphs with the path Pn.

Słowa kluczowe

EN

graph; crossing number; join product; cyclic permutation; path

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2022
• Tom: Vol. 42, no. 4
• Strony: 635--651
• Opis fizyczny: Bibliogr. 29 poz., rys., 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

Švecová 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-0002-7043-2760

Bibliografia

• [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 the join of the wheel on six vertices with a path, Carpathian J. Math. 38 (2022), no. 2, 337–346.
• [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] 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.
• [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] M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 4 (1983), no. 3, 312–316.
• [8] 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.
• [9] D.J. Kleitman, The crossing number of K5,n, J. Combinatorial Theory 9 (1970), 315–323.
• [10] 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.
• [11] M. Klešč, The join of graphs and crossing numbers, Electron. Notes in Discrete Math. 28 (2007), 349–355.
• [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šč, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001), 353–359.
• [14] 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.
• [15] 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.
• [16] M. Klešč, J. Petrillová, M. Valo, Minimal number of crossings in strong product of paths, Carpathian J. Math. 29 (2013), no. 1, 27–32.
• [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 (2020) [to appear].
• [20] 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.
• [21] M. Li, Crossing numbers of join of the graph on five vertices with n isolated vertices and paths, J. Hubei Uni. Arts Sci. 34 (2013), no. 11, 15–17.
• [22] 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.
• [23] M. Staš, Determining crossing number of join of the discrete graph with two symmetric graphs of order five, Symmetry 11 (2019), no. 2, 123.
• [24] M. Staš, On the crossing numbers of the join products of six graphs of order six with paths and cycles, Symmetry 13 (2021), no. 12, 2441.
• [25] M. Staš, Join products K2,3 + Cn, Mathematics 8 (2020), no. 6, 925.
• [26] 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.
• [27] M. Staš, The crossing numbers of join products of paths and cycles with four graphs of order five, Mathematics 9 (2021), no. 11, 1277.
• [28] 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.
• [29] 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).