Geodesic
Cyclic Permutations in Determining Crossing Numbers
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1163-1183.

Voir la notice de l'article provenant de la source Library of Science

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. Recently, the crossing numbers of join products of two graphs have been studied. In the paper, we extend know results concerning crossing numbers of join products of small graphs with discrete graphs. The crossing number of the join product G*+ Dn for the disconnected graph G* consisting of five vertices and of three edges incident with the same vertex is given. Up to now, the crossing numbers of G + Dn were done only for connected graphs G. In the paper also the crossing numbers of G*+ Pn and G* + Cn are given. The paper concludes by giving the crossing numbers of the graphs H + Dn, H + Pn, and H + Cn for four different graphs H with |E(H)| ≤ |V (H)|. The methods used in the paper are new. They are based on combinatorial properties of cyclic permutations.
Keywords: graph, drawing, crossing number, join product, cyclic permutation 
@article{DMGT_2022_42_4_a9,
     author = {Kle\v{s}\v{c}, Mari\'an and Sta\v{s}, Michal},
     title = {Cyclic {Permutations} in {Determining} {Crossing} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1163--1183},
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/}
}
TY  - JOUR
AU  - Klešč, Marián
AU  - Staš, Michal
TI  - Cyclic Permutations in Determining Crossing Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 1163
EP  - 1183
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/
LA  - en
ID  - DMGT_2022_42_4_a9
ER  - 
%0 Journal Article
%A Klešč, Marián
%A Staš, Michal
%T Cyclic Permutations in Determining Crossing Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 1163-1183
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/
%G en
%F DMGT_2022_42_4_a9
Klešč, Marián; Staš, Michal. Cyclic Permutations in Determining Crossing Numbers. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 4, pp. 1163-1183. http://geodesic.mathdoc.fr/item/DMGT_2022_42_4_a9/

[1] M.R. Garey and D.S Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 4 (1983) 312–316. https://doi.org/10.1137/0604033

[2] C. Hernández-Vélez, C. Medina and G. Salazar, The optimal drawing of K5,n, Electron. J. Combin. 21 (2014) #P4.1. https://doi.org/10.37236/2777

[3] M. Klešč, The join of graphs and crossing numbers, Electron. Notes Discrete Math. 28 (2007) 349–355. https://doi.org/10.1016/j.endm.2007.01.049

[4] M. Klešč, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Math. 310 (2010) 1475–1481. https://doi.org/10.1016/j.disc.2009.08.018

[5] M. Klešč andŠ. Schrötter, The crossing numbers of join products of paths with graphs of order four, Discuss. Math. Graph Theory 31 (2011) 321–331. https://doi.org/10.7151/dmgt.1548

[6] M. Klešč andŠ. Schrötter, The crossing number of join of paths and cycles with two graphs of order five, Lecture Notes in Comput. Sci. 7125 (2012) 160–167. https://doi.org/10.1007/978-3-642-28212-6_15

[7] M. Klešč and M. Valo, Minimum crossings in join of graphs with paths and cycles, Acta Electrotech. Inform. 12 (2012) 32–37. https://doi.org/10.2478/v10198-012-0028-0

[8] M. Klešč, J. Petrillová and M. Valo, On the crossing numbers of Cartesian products of wheels and trees, Discuss. Math. Graph Theory 37 (2017) 399–413. https://doi.org/10.7151/dmgt.1957

[9] D.J. Kleitman, The crossing number of K5,n, J. Combin. Theory Ser. B 9 (1970) 315–323. https://doi.org/10.1016/S0021-9800(70)80087-4

[10] M. Staš, On the crossing number of the join of the discrete graph with one graph of order five, Math. Model. Geom. 5 (2017) 12–19. https://doi.org/10.26456/mmg/2017-522

[11] R.D. Woodall, Cyclic-ordered graphs and Zarankiewicz’s crossing number conjecture, J. Graph Theory 17 (1993) 657–671. https://doi.org/10.1002/jgt.3190170602

[12] K. Zarankiewicz, On a problem of P. Turán concerning graphs, Fund. Math. 41 (1955) 137–145. https://doi.org/10.4064/fm-41-1-137-145