1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Cyclic Permutations in Determining Crossing Numbers

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1163 - 1183
Received: 07 Mar 2019
Accepted: 16 May 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

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

MSC 2010

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

[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 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo