On the crossing numbers of join products of W4 + Pn and W4 + Cn

• Autorzy: Stas Michal , Valiska Juraj

Identyfikatory

DOI

10.7494/OpMath.2021.41.1.95

• 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. The main aim of the paper is to give the crossing number of the join product W4 + Pn and W4 + Cn for the wheel W4 on five vertices, where Pn and Cn are the path and the cycle on n vertices, respectively. Yue et al. conjectured that the crossing number of Wm + Cn is equal to [formula], for all m,n ≥ 3, and where the Zarankiewicz’s number[formula] is defined for n ≥ 1. Recently, this conjecture was proved for W3 + Cn by Klesc. We establish the validity of this conjecture for W4 + Cn and we also offer a new conjecture for the crossing number of the join product Wm + Pn for m ≥ 3 and n ≥ 2.

Słowa kluczowe

EN

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

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2021
• Tom: Vol. 41, no. 1
• Strony: 95--112
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Stas Michal

• Technical University of Kosice Faculty of Electrical Engineering and Informatics Department of Mathematics and Theoretical Informatics 457-463 Kosice, Slovak Republic

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

autor

Valiska Juraj

• Technical University of Kosice Faculty of Electrical Engineering and Informatics Department of Mathematics and Theoretical Informatics 042-00 Kosice, Slovak Republic

• https://orcid.org/0000-+0003-+0245-+5845

Bibliografia

• [1] S. Berezny, J.Jr. Busa, Algorithm of the cyclic-order graph program (implementation and usage), J. Math. Model. and Geometry 7 (2019), no. 3, 1-8.
• [2] S. Berezny, M. Stas, 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] S. Berezny, M. Stas, On the crossing number of join of the wheel on six vertices with the discrete graph, Carpathian J. Math. 36 (2020), no. 3, 381-390.
• [4] K. Clancy, M. Haythorpe, A. Newcombe, A survey of graphs with known or bounded crossing numbers, Australas. J. Combin. 78 (2020), no. 2, 209-296.
• [5] E. Drazenska, 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. Drazenska, 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] D.S. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic. Discrete Methods 4 (1983), 312-316.
• [8] C. Hernandez-Velez, C. Medina, G. Salazar, The optimal drawing of K5,n, Electronic Journal of Combinatorics 21 (2014), no. 4, Paper 4.1, 29 pp.
• [9] P.T. Ho, On the crossing number of some complete multipartite graphs, Utilitas Math. 79 (2009), 125-143.
• [10] P.T. Ho, The crossing number of K1,m,n , Discrete Math. 308 (2008), no. 24, 5996-6002.
• [11] D.J. Kleitman, The crossing number of K5,n , J. Combinatorial Theory 9 (1970), 315-323.
• [12] M. Klesc, The crossing number of join of the special graph on six vertices with path and cycle, Discrete Math. 310 (2010), 1475-1481.
• [13] M. Klesc, The join of graphs and crossing numbers, Electron. Notes in Discrete Math. 28 (2007), 349-355.
• [14] M. Klesc, The crossing numbers of join of cycles with graphs of order four, Proc. Aplimat 2019: 18th Conference on Applied Mathematics (2019), 634-641.
• [15] M. Klesc, J. Petrillova, M. Valo, On the crossing numbers of Cartesian products of wheels and trees, Discuss. Math. Graph Theory 71 (2017), 399-413.
• [16] M. Klesc, S. Schrotter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31 (2011), no. 2, 321-331.
• [17] M. Klesc, S. Schrotter, 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. Klesc, M. Stas, Cyclic permutations in determining crossing numbers, Discuss. Math. Graph Theory (to appear).
• [19] M. Stas, On the crossing number of join of the wheel on five vertices with the discrete graph, Bull. Aust. Math. Soc. 101 (2020), no. 3, 353-361.
• [20] M. Stas, Determining crossing number of join of the discrete graph with two symmetric graphs of order five, Symmetry 11 (2019), no. 2, 1-9.
• [21] M. Stas, Join products K2,3 + Cn, Mathematics 8 (2020), no. 6, 1-9.
• [22] M. Stas, J. Petrillova, 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.
• [23] Z. Su, Y. Huang, The crossing number of Wm V Pn, J. Math. Stud. 45 (2012), no. 3, 310-314.
• [24] D.R. Woodall, Cyclic-order graphs and Zarankiewicz’s crossing number conjecture, J. Graph Theory 17 (1993), no. 6, 657-671.
• [25] W. Yue, Y. Huang, Z. Ouyang, On crossing numbers of join of W4 + Cn , Comp. Eng. Appl. 50 (2014), no. 18, 79-84.
• [26] K. Zarankiewicz, On a problem of P. Turan concerning graphs, Fundamenta Mathema-ticae 41 (1954), 137-145.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).