Opuscula Math. 42, no. 4 (2022), 635-651
https://doi.org/10.7494/OpMath.2022.42.4.635

 
Opuscula Mathematica

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

Michal Staš
Mária Švecová

Abstract. The main aim of this paper is to give the crossing number of the join product \(G^\ast+P_n\) for the disconnected graph \(G^\ast\) of order five consisting of the complete graph \(K_4\) and one isolated vertex, where \(P_n\) 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^\ast\) with the paths. Finally, by adding new edges to the graph \(G^\ast\), we are able to obtain the crossing numbers of the join products of two other graphs with the path \(P_n\).

Keywords: graph, crossing number, join product, cyclic permutation, path.

Mathematics Subject Classification: 05C10, 05C38.

Full text (pdf)

  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. https://doi.org/10.26456/mmg/2019-731
  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. https://doi.org/10.37193/CJM.2022.02.06
  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: \(22^{th}\) 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 \(37^{th}\) 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. https://doi.org/10.1137/0604033
  8. C. Hernández-Vélez, C. Medina, G. Salazar, The optimal drawing of \(K_{5,n}\), Electronic Journal of Combinatorics 21 (2014), no. 4, Paper 4.1, 29 pp. https://doi.org/10.37236/2777
  9. D.J. Kleitman, The crossing number of \(K_{5,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. https://doi.org/10.1016/j.disc.2009.08.018
  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: \(18^{th}\) 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. https://doi.org/10.1016/S0012-365X(00)00251-X
  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. https://doi.org/10.7151/dmgt.1548
  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. https://doi.org/10.7151/dmgt.2005
  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. https://doi.org/10.3390/sym11020123
  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. https://doi.org/10.3390/sym13122441
  25. M. Staš, Join products \(K_{2,3} +C_n\), Mathematics 8 (2020), no. 6, 925. https://doi.org/10.3390/math8060925
  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. http://dx.doi.org/10.5614/ejgta.2020.8.2.10
  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. https://doi.org/10.3390/math9111277
  28. M. Staš, 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. D.R. Woodall, Cyclic-order graphs and Zarankiewicz's crossing number conjecture, J. Graph Theory 17 (1993), no. 6, 657-671.
  • Michal Staš (corresponding author)
  • ORCID iD https://orcid.org/0000-0002-2837-8879
  • Technical University of Košice, Faculty of Electrical Engineering and Informatics, Department of Mathematics and Theoretical Informatics, 042 00 Košice, Slovak Republic
  • Mária Švecová
  • ORCID iD https://orcid.org/0000-0002-7043-2760
  • Technical University of Košice, Faculty of Electrical Engineering and Informatics, Department of Mathematics and Theoretical Informatics, 042 00 Košice, Slovak Republic
  • Communicated by Andrzej Żak.
  • Received: 2021-07-07.
  • Revised: 2022-05-10.
  • Accepted: 2022-05-15.
  • Published online: 2022-06-30.
Opuscula Mathematica - cover

Cite this article as:
Michal Staš, Mária Švecová, The crossing numbers of join products of paths with three graphs of order five, Opuscula Math. 42, no. 4 (2022), 635-651, https://doi.org/10.7494/OpMath.2022.42.4.635

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

We advise that this website uses cookies to help us understand how the site is used. All data is anonymized. Recent versions of popular browsers provide users with control over cookies, allowing them to set their preferences to accept or reject all cookies or specific ones.