Rotation and Crossing Numbers for Join Products
- PDF / 449,480 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 27 Downloads / 157 Views
Rotation and Crossing Numbers for Join Products Zongpeng Ding1 Received: 20 August 2019 / Revised: 4 February 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract Computing the crossing number of a graph is NP-hard. In the paper, for a disconnected 6-vertex graph Q = C5 ∪ K 1 , we obtain the crossing number Z (6, n) + n2 of the graph Q n which is the join product of Q with the discrete graph by introducing the “rotation” method. Moreover, we give crossing numbers for join products of Q with the path and the cycle. Besides, we also get directly crossing numbers for join products of some connected 6-vertex graphs with the path and the cycle, some of which were studied by M. Klešˇc, D. Kravecová, and J. Petrillová. Keywords Rotation · Disconnected graph · Crossing number · Join product · Drawing Mathematics Subject Classification 05C10 · 05C62
1 Introduction This work is motivated by Clancy et al. [4] their survey on graphs with known or bounded crossing numbers very recently. In [4], Clancy et al. collected all known results concerning crossing numbers of join products involving 6-vertex graphs. However, these 6-vertex graphs have only been considered in-depth for connected 6-vertex graphs and are only known for some cases. A drawing of G is good if it satisfies the following assumptions: (a) three edges do not cross in a point, (b) adjacent edges do not cross each other, (c) two edges
Communicated by Xueliang Li. The work was supported by the National Natural Science Foundation of China (Grant No. 11871206), the Scientific Research Fund of Hunan Provincial Education Department (Grant No.19B116).
B 1
Zongpeng Ding [email protected] Department of Mathematics, Hunan First Normal University, Changsha 410205, Hunan, People’s Republic of China
123
Z. Ding
do not cross more than once, and (d) edge does not cross itself. For a good drawing D of G, cr D (G) is denoted as the number of crossings in the drawing in the plane. The crossing number cr (G) of G is the minimum number of crossings in any good drawing of G. If cr D (G) = cr (G), the drawing D is said to be optimal. There are many applications for the theory of crossing number, see references [1,12], and [13]. However, in general, finding the crossing number is NP-hard [6], and hence difficult to solve; this is even true for graphs constructed by adding a single edge to a planar graph [2]. Finding the crossing number is notoriously difficult, even for small graphs; indeed, the crossing number for K 13 is still an open problem [11]. To date, crossing numbers have only been proved for a small number of graph families. For some other graph families, bounds have been established which are usually conjectured (but not proved) to be exact [7]. Let n K 1 , Pn , and Cn , respectively, denote the discrete graph, the path, and the cycle on n vertices. For two graphs G 1 and G 2 , their join product is denoted by G 1 + G 2 . The join product has special structure, for example, the complete bipartite graph K p,q can be regar
Data Loading...
