Opuscula Math. 40, no. 3 (2020), 383-397
https://doi.org/10.7494/OpMath.2020.40.3.383

Opuscula Mathematica

# On the crossing numbers of join products of five graphs of order six with the discrete graph

Michal Staš

Abstract. The main purpose of this article is broaden known results concerning crossing numbers for join of graphs of order six. We give the crossing number of the join product $$G^{\ast} + D_n$$, where the disconnected graph $$G^{\ast}$$ of order six consists of one isolated vertex and of one edge joining two nonadjacent vertices of the $$5$$-cycle. In our proof, the idea of cyclic permutations and their combinatorial properties will be used. Finally, by adding new edges to the graph $$G^{\ast}$$, the crossing numbers of $$G_i+D_n$$ for four other graphs $$G_i$$ of order six will be also established.

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

Mathematics Subject Classification: 05C10, 05C38.

Full text (pdf)

1. Š. Berežný, J. Buša Jr., Algorithm of the cyclic-order graph program (implementation and usage), Math. Model. Geom. 7 (2019) 3, 1-8.
2. Š. Berežný, M. Staš, Cyclic permutations and crossing numbers of join products of symmetric graph of order six, Carpathian J. Math. 34 (2018) 2, 143-155.
3. C. Hernández-Vélez, C. Medina, G. Salazar, The optimal drawing of $$K_{5,n}$$, Electronic Journal of Combinatorics 21 (2014) 4, Article no. P4.1.
4. D.J. Kleitman, The crossing number of $$K_{5,n}$$, J. Combinatorial Theory 9 (1970), 315-323.
5. M. Klešč, The crossing numbers of Cartesian products of paths with 5-vertex graphs, Discrete Math. 233 (2001), 353-359.
6. M. Klešč, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Math. 310 (2010) 9, 1475-1481.
7. M. Klešč, The join of graphs and crossing numbers, Electronic Notes in Discrete Mathematics 28 (2007), 349-355.
8. 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.
9. M. Klešč, Š. Schrötter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31 (2011) 2, 321-331.
10. 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.
11. M. Staš, On the crossing number of the join of the discrete graph with one graph of order five, Math. Model. Geom. 5 (2017) 2, 12-19.
12. M. Staš, Cyclic permutations: Crossing numbers of the join products of graphs, Proc. Aplimat 2018: $$17^{th}$$ Conference on Applied Mathematics (2018), 979-987.
13. M. Staš, Determining crossing numbers of graphs of order six using cyclic permutations, Bull. Aust. Math. Soc. 98 (2018) 3, 353-362.
14. M. Staš, Determining crossing number of join of the discrete graph with two symmetric graphs of order five, Symmetry 11 (2019) 2, 1-9.
15. D.R. Woodall, Cyclic-order graphs and Zarankiewicz's crossing number conjecture, J. Graph Theory 17 (1993), 657-671.
• Communicated by Ingo Schiermeyer.
• Revised: 2020-01-18.
• Accepted: 2020-02-25.
• Published online: 2020-04-04. 