Article in volume
Authors:
Title:
Cyclic permutations in determining crossing numbers
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1163-1183
Received: 2019-03-07 , Revised: 2020-05-12 , Accepted: 2020-05-16 , Available online: 2020-09-07 , https://doi.org/10.7151/dmgt.2351
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^* + D_n$ 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 + D_n$ were done
only for connected graphs $G$. In the paper also the crossing numbers of
$G^* + P_n$ and $G^* + C_n$ are given. The paper concludes by giving the
crossing numbers of the graphs $H + D_n$, $H + P_n$, and $H + C_n$ for four
different graphs $H$ with $|E(H)| \leq |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
References:
- 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 - C. Hernández-Vélez, C. Medina and G. Salazar, The optimal drawing of $K_{5,n}$, Electron. J. Combin. 21 (2014) #P4.1.
https://doi.org/10.37236/2777 - 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 - 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 - 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 - 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 - 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 - 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 - D.J. Kleitman, The crossing number of $K_{5,n}$, J. Combin. Theory Ser. B 9 (1970) 315–323.
https://doi.org/10.1016/S0021-9800(70)80087-4 - 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 - 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 - 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
Close