The Crossing Number of Join of a Special Disconnected 6-Vertex Graph with Cycle

Abstract

The crossing number of a graph G, $cr\left(G\right)$, is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. There are almost no results concerning crossing number of join of a disconnected 6-vertex graph with cycle. The main aim of this paper is to give the crossing number of the join product $Q+C_n$ for the disconnected 6-vertex graph Q consisting of the two 3-cycles, where $C_n$ is the cycle on n vertices.

1. Introduction

All graphs considered here are simple, finite and undirected. For any graph G, let $V\left(G\right)$ and $E\left(G\right)$ denote its vertex set and edge set, respectively. A drawing of a graph G is a mapping D that assigns to each vertex in $V\left(G\right)$ a distinct point in the plane, and to each edge $uv$ in G a continuous arc connecting $D\left(u\right)$ and $D\left(v\right)$, not passing through the image of any other vertex. For simplicity, we impose the following conditions on a drawing: (a) no three edges have an interior point in common, (b) if two edges share an interior point p, then they cross at p, and (c) any two edges of a drawing have only a finite number of crossings (common interior points). We call a drawing that meets the above conditions a good drawing.

For any good drawing D of G, let $cr\left(D\right)$ denote the number of crossings in D, and the crossing number of G, denoted by $cr\left(G\right)$, is the minimum value of $cr\left(D\right)$s among all possible good drawings D of G. The problem of reducing the number of crossings is interesting in many areas.

Let $A,B$ and C be mutually edge-disjoint subgraphs of G; we denote by $c{r}_D(A,B)$ the number of crossings between edges of A and edges of B and by $c{r}_D\left(A\right)$ the number of crossings among edges of A in $D.$ It is easy to obtain the following property.

Property 1.

Let D be a good drawing of the graph G; let $A,B$ and C be mutually edge-disjoint subgraphs of G; then we have

(1) 

$c{r}_D(A\cup B)=c{r}_D\left(A\right)+c{r}_D\left(B\right)+c{r}_D(A,B),$ and

(2) 

$c{r}_D(A\cup B,C)$ = $c{r}_D(A,C)$ + $c{r}_D(B,C).$

In general, finding the crossing number is NP -hard [1]. It has been long conjectured in [2] that the crossing number of the complete bipartite graph $K_{m,n}$ is

$$cr\left(K_{m,n}\right)=\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \triangleq Z(m,n).$$

(1)

This conjecture has been verified for $min\{m,n\}\le 6$ [3] and for $m=7$ and $n\le 10$ [4]. Using Kleitman’s result [3], the crossing number of $K_{5,n+1}\setminus e$ was determined in [5].

Let $C_n$ be the cycle of length n, $P_n$ be the path of length $n-1$ and $n{K}_1$ be the discrete graph on n isolated vertices. For two graphs $G_1$ and $G_2$, their join product is denoted by $G_1+G_2$. For the join product of two graphs, papers [6,7,8,9,10,11,12] gave the exact values for crossing numbers of $G_1+G_2$ for some connected graphs $G_1$ such that $\left|V\right(G_1\left)\right|\le 6$, and $G_2$ is some special graphs, such as $n{K}_1$, $P_n$ or $C_n$. Due to the special topological structure for the disconnected graph, there are almost no results concerning crossing number of join of a disconnected 6-vertex graph with cycle. Very recently, some results about $G_1+G_2$ have been produced that deal with the case in which 5-vertex or 6-vertex graph $G_1$ is disconnected; see [13,14,15,16]. Further details can be found in reference [17].

The purpose of this article is to extend the known results concerning this topic to new 6-vertex disconnected graphs. In this paper, we determine the crossing number for the join of the graph $n{K}_1$ with the special disconnected graph Q consisting of the two 3-cycles. This result enables us to give the crossing numbers of $Q+P_n$ and $Q+C_n.$ Our results are as follows:

Theorem 1.

For $n\ge 1,$ we have

$$cr(Q+n{K}_1)=\left\{\begin{array}{cc}0,\hfill & n=1;\hfill \\ Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill & n\ge 2\mathrm{and}n\mathit{is}\mathit{even};\hfill \\ Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2,\hfill & n\ge 2\mathit{and}n\mathit{is}\mathit{odd}.\hfill \end{array}\right.$$

Corollary 1.

$cr(Q+P_1)=0,$$cr(Q+P_2)=2$; for $n\ge 3,$ we have

$$cr(Q+P_n)=cr(Q+C_n)=\left\{\begin{array}{cc}Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill & n\mathit{is}\mathit{even};\hfill \\ Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2,\hfill & n\mathit{is}\mathit{odd}.\hfill \end{array}\right.$$

In the proofs of the paper, we will often use the term “region” also in nonplanar drawings. In this case, crossings are considered to be vertices of the “face”.

2. The Crossing Number of $\mathbf{Q}+{\mathbf{C}}_{\mathbf{n}}$

The special disconnected graph Q consists of two 3-cycles; see Figure 1. The graph $Q+n{K}_1$ consists of one copy of Q and n isolated vertices $t_1,...,t_n$ where each $t_i$$(i=1,\cdots ,n)$ is adjacent to $v_j$$(1\le j\le 6).$ For $i=1,\cdots ,n$; let $T_i$ denote the subgraph induced by six edges incident with the vertex $t_i.$ Clearly,

$$Q+n{K}_1=Q\cup K_{6,n},E(Q+n{K}_1)=E\left(Q\right)\cup \left({\displaystyle \bigcup _{i=1}^n}{T}_i\right).$$

Lemma 1.

$cr(Q+K_1)=0$, $cr(Q+2K_1)=2$ and $cr(Q+3K_1)=6.$

Proof. 

The planar subdrawing of graph Q is shown in Figure 1. It can be easily seen from Figure 2 that the graph $Q+K_1$ is planar and thus $cr(Q+K_1)=0.$

The good drawing in Figure 3 shows that $cr(Q+2K_1)\le 2.$ We are now going to prove the reverse inequality by assuming to the contrary that there exists a good drawing $\varphi$ of $Q+2K_1$ with $c{r}_{\varphi }(Q+2K_1)<2.$ Then there must exist i$(i=1\mathrm{or}2)$ such that $c{r}_{\varphi }(Q,T_i)=0$; otherwise, $c{r}_{\varphi }(Q,T_i)\ge 1$ for $i=1,2$ and $c{r}_{\varphi }(Q+2K_1)={\displaystyle \sum _{i=1}^2}c{r}_{\varphi }(Q,T_i)\ge 2.$ Without loss of generality, assume that $i=1$; then the subdrawing of $Q\cup T_1$ induced by $\varphi$ must be as shown in Figure 2, and the plane has been divided into seven regions; for each region, there are at most four vertices of Q that lie on its boundary. Now consider $t_2$; no matter which region $t_2$ lies in, there will be at least two crossings between the edges of $T_2$ and the edges of $Q\cup T_1,$ thus $c{r}_{\varphi }(Q+2K_1)\ge 2,$ and this contradiction completes the proof that $cr(Q+2K_1)=2.$

On the one hand, we can obtain that $cr(Q+3K_1)\ge 6$ since $Q+3K_1$ contains $K_{3,6}$ as a subgraph with $cr\left(K_{3,6}\right)=6.$ On the other hand, the good drawing in Figure 4 shows that $cr(Q+3K_1)\le 6.$ The proof is completed.   □

Lemma 2.

Let $n\ge 3$ and n be odd; if $cr(Q+(n-1)K_1)=Z(6,n-1)+2\lfloor \frac{n-1}{2}\rfloor ,$ then $cr(Q+n{K}_1)=Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2.$

Proof. 

We will display a drawing $\varphi$ of $Q+n{K}_1$ in the plane such that $c{r}_{\varphi }(Q+n{K}_1)=Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2.$ The desired drawing $\varphi$ is constructed as follows (see Figure 5, when n is odd):

$\left(i\right)$ Set all vertices of Q on the y-axis.

$\left(ii\right)$ Set $\lfloor \frac{n}{2}\rfloor$ isolated vertices on the negative x-axis and $\lceil \frac{n}{2}\rceil$ isolated vertices on the positive x-axis.

Then it is not difficult to see that $c{r}_{\varphi }(Q+n{K}_1)=Z(6,n)+2\lceil \frac{n}{2}\rceil -4=Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2$ and so $cr(Q+n{K}_1)\le Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2.$

Now we continue to prove the reverse inequality, let $\varphi$ be an arbitrary good drawing of $Q+n{K}_1,$ and let $r_{\varphi }\left(t_i\right)$ denote the number of crossings on the edges adjacent to $t_i$ under $\varphi .$ Then we have

$${\displaystyle \sum _{i=1}^n}{r}_{\varphi }\left(t_i\right)\ge 2c{r}_{\varphi }\left(K_{6,n}\right)\ge 2Z(6,n).$$

Without loss of generality, assume that $r_{\varphi }\left(t_1\right)=\underset{i}{max}\left\{r_{\varphi }\left(t_i\right)\right\};$ then it follows from the above equation that $r_{\varphi }\left(t_1\right)\ge \frac{2Z(6,n)}{n}=3n-6+\frac{3}{n};$ furthermore, we can have $r_{\varphi }\left(t_1\right)\ge 3n-5$ since $r_{\varphi }\left(t_1\right)$ must be an integer; thus

$$\begin{array}{ccc}c{r}_{\varphi }(Q+n{K}_1)\hfill & =\hfill & c{r}_{\varphi }(Q+(n-1)K_1)+r_{\varphi }\left(t_1\right)\hfill \\ & \ge \hfill & Z(6,n-1)+2\lfloor \frac{n-1}{2}\rfloor +3n-5\hfill \\ & =\hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2.\hfill \end{array}$$

Since $\varphi$ is an arbitrary good drawing of $Q+n{K}_1,$ we can obtain that $cr(Q+n{K}_1)\ge Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2$ and the proof is finished.  □

Lemma 3.

Let $n\ge 2$ and n be even; if the equality $cr(Q+t{K}_1)=Z(6,t)+2\lfloor \frac{t}{2}\rfloor$ holds for even t $(t<n),$ then we have $cr(Q+n{K}_1)=Z(6,n)+2\lfloor \frac{n}{2}\rfloor .$

Proof. 

When n is even, the good drawing in Figure 6 shows that $cr(Q+n{K}_1)\le Z(6,n)+2\lfloor \frac{n}{2}\rfloor .$ Now we are going to prove the reverse inequality by assuming to the contrary that there is a good drawing D of $Q+n{K}_1$ that satisfies

$$c{r}_D(Q+n{K}_1)<Z(6,n)+2\lfloor \frac{n}{2}\rfloor$$

(2)

 □

Claim 1.

For $1\le i\ne j\le n,$ there is at least one crossing between the edges of $T_i$ and $T_j;$ that is, $c{r}_D(T_i,T_j)\ge 1.$

Proof. 

Without loss of generality, assume to the contrary that $c{r}_D(T_n,T_{n-1})=0.$ Notice that the subgraph $T_n\cup T_{n-1}\cup T_i$ is isomorphic to the complete bipartite graph $K_{3,6}$ whose crossing number is 6; thus, for $1\le i\le n-2,$ we have

$$\begin{array}{ccc}c{r}_D(T_n\cup T_{n-1},T_i)\hfill & =\hfill & c{r}_D(T_n\cup T_{n-1}\cup T_i)-c{r}_D(T_n\cup T_{n-1})-c{r}_D\left(T_i\right)\hfill \\ & =\hfill & c{r}_D\left(K_{3,6}\right)-c{r}_D(T_n\cup T_{n-1})-c{r}_D\left(T_i\right)\hfill \\ & \ge \hfill & 6.\hfill \end{array}$$

Notice that the subgraph $Q\cup \left({\displaystyle \bigcup _{i=1}^{n-2}}{T}_i\right)$ is isomorphic to $Q+(n-2)K_1;$ furthermore, it is seen from Figure 3 that there are at least two crossings made by the edges of Q and $T_n\cup T_{n-1}$ in $D;$ these observations combined with Property 1 enforce that

$$\begin{array}{ccc}c{r}_D(Q+n{K}_1)\hfill & =\hfill & c{r}_D\left(T_n\cup T_{n-1}\cup Q\cup \left({\displaystyle \bigcup _{i=1}^{n-2}}{T}_i\right)\right)\hfill \\ & =\hfill & c{r}_D\left(T_n\cup T_{n-1},{\displaystyle \bigcup _{i=1}^{n-2}}{T}_i\right)+c{r}_D(T_n\cup T_{n-1},Q)\hfill \\ & & +c{r}_D\left(Q\cup \left({\displaystyle \bigcup _{i=1}^{n-2}}{T}_i\right)\right)+c{r}_D(T_n\cup T_{n-1})\hfill \\ & \ge \hfill & 6(n-2)+2+Z(6,n-2)+n-2\hfill \\ & \ge \hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill \end{array}$$

(3)

This is contradictory to Equation (2); thus, $c{r}_D(T_i,T_j)\ge 1$ for $1\le i\ne j\le n.$  □

Claim 2.

There must exist $T_i$ such that $c{r}_D(T_i,Q)=0.$

Proof. 

Assume to the contrary that $c{r}_D(T_i,Q)\ge 1$ for $1\le i\le n;$ then we have

$$c{r}_D(Q+n{K}_1)=c{r}_D\left(Q\right)+c{r}_D\left({\displaystyle \bigcup _{i=1}^n}{T}_i\right)+{\displaystyle \sum _{i=1}^n}c{r}_D(T_i,Q)\ge Z(6,n)+n,$$

This is contradictory to Equation (2) and thus there must exist $T_i$ such that $c{r}_D(T_i,Q)=0.$ Without loss of generality, we assume that $c{r}_D(T_n,Q)=0.$  □

Claim 3.

Q can not have self crossings under the drawing $D;$ that is, $c{r}_D\left(Q\right)=0.$

Proof. 

Assume to the contrary that $c{r}_D\left(Q\right)\ge 1.$ Notice that Q consists of two edge disjoint 3-cycles and the edges which belong to the same 3-cycle cannot cross each other under the good drawing; thus, the crossings of Q must made by the edges of different 3-cycles. Combined with claim 2, in $D,$ there is a region with all the vertices of Q lying on its boundary; then there are only two possibilities of the subdrawing of Q induced by $D,$ see Figure 7 and Figure 8, and the subdrawing of $T_n\cup Q$ induced by D must be one of the possibilities shown in Figure 9 or Figure 10.

If the subdrawing of $T_n\cup Q$ induced by D is as shown in Figure 9, it is not difficult to see that the plane has been divided into several regions; for each region, there are at most two vertices of Q that lie on its boundary. Thus, for $1\le i\le n-1,$ we have $c{r}_D(T_i,T_n\cup Q)\ge 4,$ and

$$\begin{array}{ccc}c{r}_D(Q+n{K}_1)\hfill & =\hfill & c{r}_D\left({\displaystyle \bigcup _{i=1}^{n-1}}{T}_i\right)+{\displaystyle \sum _{i=1}^{n-1}}c{r}_D(Q\cup T_n,T_i)+c{r}_D(Q\cup T_n)\hfill \\ & \ge \hfill & Z(6,n-1)+4(n-1)\hfill \\ & \ge \hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill \end{array}$$

(4)

which conflicts with Equation (2). A contradiction can also be made if the subdrawing of $T_n\cup Q$ induced by D is as shown in Figure 10 with arguments similar to the above; thus, the claim is true.  □

Let $H=T_n\cup Q;$ it follows from Claims 2 and 3 that there is only one possibility of the subdrawing of H under $D;$ see Figure 2. The plane has been divided into several regions such that there are at most four vertices of Q that lie on the boundary of each region; therefore, for any $1\le i\le n-1,$ we have $c{r}_D(T_i,H)\ge 2$ no matter which region $t_i$ lies in. Moreover, we can obtain from Figure 2 and Claim 1 that $c{r}_D(T_i,H)\ne 3$ for any $1\le i\le n-1,$ and that there must exist $T_i$ such that $c{r}_D(T_i,H)<4$ according to Equation (4). Hence, we can assert that there must exist $T_i$ that admits $c{r}_D(T_i,H)=2.$ Without loss of generality, assume that $c{r}_D(T_{n-1},H)=2.$ On the other hand, note that $2=c{r}_D(T_{n-1},H)=c{r}_D(T_{n-1},Q)+c{r}_D(T_{n-1},T_n)$ and $c{r}_D(T_{n-1},T_n)\ge 1;$ then the following two cases are discussed.

Case 1 $c{r}_D(T_{n-1},Q)=1.$

$c{r}_D(T_{n-1},T_n)=1;$ this conclusion enforces that there is only one possibility of the subdrawing of $T_n\cup T_{n-1}\cup Q$ induced by $D;$ see Figure 11. It is not a difficult task to verify that, for any $1\le i\le n-2,$$c{r}_D(T_{n-1}\cup T_n,T_i)\ge 5$ holds no matter which region $t_i$ lies in and the equality holds if and only if the vertex $t_i$ lies in one of the regions labelled with $a_1,a_2,a_3$ or $a_4.$ On the other hand, Equation (3) implies that there exist i such that $c{r}_D(T_{n-1}\cup T_n,T_i)\le 5.$ Hence, there must be i such that $c{r}_D(T_{n-1}\cup T_n,T_i)=5,$ without loss of generality; assume $c{r}_D(T_{n-1}\cup T_n,T_{n-2})=5.$ Combined with the above arguments, it is known that $t_{n-2}$ must lie in the regions labelled with $a_1,a_2,a_3$ or $a_4.$

The rotation of a vertex $t_i$ in the drawing D (${\pi }_D\left(t_i\right)$) is the cyclic permutation that records the (cyclic) clockwise order in which the edges leave $t_i$; see Ding [14]. We use the notation (123456) if the clockwise order with the edges incident with the vertex $t_i$ is $t_i{v}_1,t_i{v}_2,t_i{v}_3$, $t_i{v}_4$, $t_i{v}_5$ and $t_i{v}_6.$

If $t_{n-2}$ lies in the region $a_4,$ one can see that there are exactly two vertices of Q that lie on its boundary and there are two possibilities for joining edge $t_{n-2}{v}_j$$(j=1,2,5,6)$, respectively. Thus, there are 16 possible drawings of $T_{n-2}\cup T_{n-1}\cup H;$ however, we carefully verified these 16 drawings; it is not difficult to verify that four possibilities of them violate the definition of good drawing and one of them violates Claim 1. In the remaining 11 drawings of $T_{n-2}\cup T_{n-1}\cup H,$${\pi }_D\left(t_{n-2}\right)$ must be (154623), (145623), (164523), (165423), (164532), (145632), (154632), (135462), (136452), (134652) or (136542).

Now we consider that $t_{n-2}$ lie in the region $a_4.$

Subcase 1.1 If ${\pi }_D\left(t_{n-2}\right)=\left(154623\right)$, see Figure 12, then for any $1\le i\le n-3,$ it is a tedious task to prove that $c{r}_D(T_i,T_n\cup T_{n-1}\cup T_{n-2}\cup Q)\ge 10$ no matter which region $t_i$ lies in; moreover, one can see from Figure 12 that there are eight crossings on $T_n\cup T_{n-1}\cup T_{n-2}\cup Q;$ thus

$$\begin{array}{ccc}c{r}_D(Q+n{K}_1)\hfill & =\hfill & c{r}_D\left({\displaystyle \bigcup _{i=1}^{n-3}}{T}_i\right)+{\displaystyle \sum _{i=1}^{n-3}}c{r}_D(T_n\cup T_{n-1}\cup T_{n-2}\cup Q,T_i)\hfill \\ & & +c{r}_D(T_n\cup T_{n-1}\cup T_{n-2}\cup Q)\hfill \\ & \ge \hfill & Z(6,n-3)+10(n-3)+8\hfill \\ & \ge \hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill \end{array}$$

(5)

This is contradictory to Equation (2).

Subcase 1.2 If ${\pi }_D\left(t_{n-2}\right)=\left(145623\right)$, see Figure 13, firstly, we can obtain that, for any $1\le i\le n-3,$$c{r}_D(T_i,T_n\cup T_{n-1}\cup T_{n-2}\cup Q)\ge 10$ except when $t_i$ lies in the regions labelled with $a.$ Moreover, if there exists $t_i$ such that $c{r}_D(T_i,T_n\cup T_{n-1}\cup T_{n-2}\cup Q)<10,$ then the vertex $t_i$ must lie in the region labelled a and $c{r}_D(T_i,T_n\cup T_{n-1})=7.$ This observation combined with our former arguments enforce that if there is a $t_i$ such that $c{r}_D(T_i,T_n\cup T_{n-1})=5;$ then, there must exist at least another $t_j$ such that $c{r}_D(T_j,T_n\cup T_{n-1})=7.$

Suppose the number of these $t_i$ that admits $c{r}_D(T_i,T_n\cup T_{n-1})=5$ is $t;$ then the number of $t_j$ that admits $c{r}_D(T_j,T_n\cup T_{n-1})=7$ is $t+k$$(k\ge 0),$ and the $n-2-2t-k$ other $t_l$ must satisfy $c{r}_D(T_l,T_n\cup T_{n-1})\ge 6;$ therefore,

$$\begin{array}{ccc}c{r}_D(Q+n{K}_1)\hfill & =\hfill & c{r}_D(Q\cup {\displaystyle \bigcup _{i=1}^{n-2}}{T}_i)+{\displaystyle \sum _{i=1}^{n-2}}c{r}_D(T_n\cup T_{n-1},T_i)+c{r}_D(T_{n-1}\cup T_n,Q)\hfill \\ & & +c{r}_D(T_n\cup T_{n-1})\hfill \\ & \ge \hfill & Z(6,n-2)+2\lfloor \frac{n-2}{2}\rfloor +5t+7(t+k)+6(n-2t-k-2)+2\hfill \\ & \ge \hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill \end{array}$$

This contradicts Equation (2). Through repeated careful verification, similar contradictions can be obtained if ${\pi }_D\left(t_{n-2}\right)$ = (164523), (165423), (164532), (145632), (154632), (135462), (136452), (134652) or (136542), respectively. We omit the details due to the argument being tedious.

In the subdrawing of $T_{n-1}\cup T_n$ induced by $D,$ observe that the boundaries of the three regions $a_1,a_2$ and $a_3$ are exactly the same, then we only need to consider one of them, without loss of generality; assume that $t_{n-2}$ lies in the region labelled $a_3,$ and there are 16 possible drawings of $T_{n-2}\cup T_{n-1}\cup H$ through similar careful analysis. At this time, ${\pi }_D\left(t_{n-2}\right)$ must be (153462), (153426), (165342), (163542), (135462), (135426), (163452), (134526), (154326), (154362), (164532), (145362), (145326), (164352), (143562) or (143526).

Now we consider that $t_{n-2}$ lies in the region $a_1,a_2$ or $a_3$. Note that there are 16 rotations of $t_{n-2}$ that need to be discussed.

Subcase 1.3 If ${\pi }_D\left(t_{n-2}\right)$ = (153462), see Figure 14, then for any $1\le i\le n-3,$ it is a tedious task to prove that $c{r}_D(T_i,T_n\cup T_{n-1}\cup T_{n-2})\ge 9$ no matter which region $t_i$ lies in; moreover, $c{r}_D(T_n\cup T_{n-1}\cup T_{n-2})=6$ and $c{r}_D(T_n\cup T_{n-1}\cup T_{n-2},Q)=7$. With Lemma 3, we assume that $cr(Q+(n-4)K_1)=Z(6,n-4)+2\lfloor \frac{n-4}{2}\rfloor ;$ then $cr(Q+(n-3)K_1)=Z(6,n-3)+2\lfloor \frac{n-3}{2}\rfloor -2$ due to Lemma 2. Thus

$$\begin{array}{ccc}c{r}_D(Q+n{K}_1)\hfill & =\hfill & c{r}_D({\displaystyle \bigcup _{i=1}^{n-3}}{T}_i\cup Q)+{\displaystyle \sum _{i=1}^{n-3}}c{r}_D(T_n\cup T_{n-1}\cup T_{n-2},T_i)\hfill \\ & & +c{r}_D(T_n\cup T_{n-1}\cup T_{n-2},Q)+c{r}_D(T_n\cup T_{n-1}\cup T_{n-2})\hfill \\ & \ge \hfill & Z(6,n-3)+2\lfloor \frac{n-3}{2}\rfloor -2+9(n-3)+7+6\hfill \\ & \ge \hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill \end{array}$$

This is contradictory to Equation (2). Through careful verification, similar contradictions can be obtained if ${\pi }_D\left(t_{n-2}\right)$ = (164352) or (143562), respectively.

Subcase 1.4 When ${\pi }_D\left(t_{n-2}\right)=$ (165342), (135462), (163542) or (164532), for $1\le i\le n-3$, either $c{r}_D(T_i,T_n\cup T_{n-1}\cup T_{n-2}\cup Q)\ge 10$ no matter which region $t_i$ lies in or there exist $T_i$ such that $c{r}_D(T_i,T_n\cup T_{n-1}\cup T_{n-2}\cup Q)\le 9$; in this case, one can find that we must have $c{r}_D(T_i,T_n\cup T_{n-1})=7.$ In the former case, we proceed by arguments analogous to that of subcase 1.1; in the latter, we use proofs similar to that of subcase 1.2. Eventually we can always obtain a contradiction by careful inspection. These details are omitted and left to the reader.

Subcase 1.5 If ${\pi }_D\left(t_{n-2}\right)$ = (143526), there exist some $T_i$; say $T_{n-3}$, such that $c{r}_D(T_{n-3},T_n\cup T_{n-1}\cup T_{n-2})=8$ and $c{r}_D(T_{n-3},T_n\cup T_{n-1})\ne 7$. At this time, $t_{n-3}$ lies in $\beta$ and ${\pi }_D\left(t_{n-3}\right)$ = (164523) or (145623). See Figure 15; then for any $1\le i\le n-4,$ it is a tedious task to prove that $c{r}_D(T_i\cup T_n\cup T_{n-1}\cup T_{n-2}\cup T_{n-3})\ge 24$ no matter which region $t_i$ lies in; moreover, $c{r}_D(T_n\cup T_{n-1}\cup T_{n-2}\cup T_{n-3},Q)=5$. Thus

$$\begin{array}{ccc}c{r}_D(Q+n{K}_1)\hfill & =\hfill & c{r}_D({\displaystyle \bigcup _{i=1}^{n-4}}{T}_i\cup Q)+{\displaystyle \sum _{i=1}^{n-4}}c{r}_D({\displaystyle \bigcup _{j=n-3}^n}{T}_j\cup T_i)\hfill \\ & & +c{r}_D({\displaystyle \bigcup _{j=n-3}^n}{T}_j,Q)\hfill \\ & \ge \hfill & Z(6,n-4)+2\lfloor \frac{n-4}{2}\rfloor +24(n-4)+5\hfill \\ & \ge \hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill \end{array}$$

This is contradictory to Equation (2). Similar contradictions can be obtained if ${\pi }_D\left(t_{n-2}\right)$ is any one of the remaining eight rotations.

Case 2$c{r}_D(Q,T_{n-1})=0.$

Then $c{r}_D(T_n,T_{n-1})=2,$ and there are exactly two possibilities of the induced subdrawing of $T_{n-1}\cup T_n$ under $D;$ see Figure 16 and Figure 17.

Clearly, $c{r}_D(T_n\cup T_{n-1}\cup Q)\ge c{r}_D(T_n,T_{n-1})=2.$ Then, we can assert that there must exist $t_i$ such that $c{r}_D(T_i,T_n\cup T_{n-1}\cup Q)\le 6,$ or else we have $c{r}_D(T_i,T_n\cup T_{n-1}\cup Q)\ge 7$ for any $1\le i\le n-2$ and

$$\begin{array}{ccc}c{r}_D(Q+n{K}_1)\hfill & =\hfill & c{r}_D\left({\displaystyle \bigcup _{i=1}^{n-2}}{T}_i\right)+{\displaystyle \sum _{i=1}^{n-2}}c{r}_D(T_n\cup T_{n-1}\cup Q,T_i)\hfill \\ & & +c{r}_D(T_n\cup T_{n-1}\cup Q)\hfill \\ & \ge \hfill & Z(6,n-2)+7(n-2)+2\hfill \\ & \ge \hfill & Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill \end{array}$$

(6)

This is contradictory to Equation (2).

Subcase 2.1 The induced subdrawing of $T_{n-1}\cup T_n$ under D is shown in Figure 16. It can be seen that $c{r}_D(T_i,T_n\cup T_{n-1}\cup Q)\ge 4$ for $1\le i\le n-2$. Observe that $c{r}_D(Q,T_{n-1})=0;$ if there exist $t_i$ such that $c{r}_D(T_i,Q\cup T_{n-1})=2$ and $c{r}_D(T_i,T_{n-1})=1,$ then this case is similar to that of Case 1. This implies that $c{r}_D(T_i,T_n\cup T_{n-1}\cup Q)\ne 5.$ Furthermore, Equation (6) implies that there must exist $t_i$ such that $c{r}_D(T_i,T_n\cup T_{n-1}\cup Q)=4$ or $c{r}_D(T_i,T_n\cup T_{n-1}\cup Q)=6,$ without loss of generality; assume that $i=n-2.$

Then there are only two possibilities of the induced subdrawing of $T_n\cup T_{n-1}\cup T_{n-2}\cup Q$ under $D;$ see Figure 18 and Figure 19. If the induced subdrawing of $T_n\cup T_{n-1}\cup T_{n-2}\cup Q$ under D is as shown in Figure 18, then for $1\le i\le n-3,$ one can obtain that $c{r}_D(T_i,T_n\cup T_{n-1}\cup T_{n-2}\cup Q)\ge 10$ no matter which region $t_i$ lies in and a contradiction can be obtained according to Equation (5). If the induced subdrawing of $T_n\cup T_{n-1}\cup T_{n-2}\cup Q$ under D is as shown in Figure 19, a contradiction similar to Case 1.2 can be obtained and the proof is omitted.

Subcase 2.2 If the induced subdrawing of $T_{n-1}\cup T_n$ under D is shown in Figure 17, it is not difficult to find that for $1\le i\le n-2,$$c{r}_D(T_i,T_n\cup T_{n-1})\ge 6$ and there is a contradiction with Equation (3).

In all, these contradictions enforce that $c{r}_D(Q+n{K}_1)\ge Z(6,n)+2\lfloor \frac{n}{2}\rfloor$ for any good drawing $D.$

Proof 

(Proof of Theorem 1). It is easily obtained from Lemmas 1, 2 and 3 that Theorem 1 holds.  □

Proof 

(Proof of Corollary 1). On the one hand, it is easy to see that $Q+C_n$ (respectively, $Q+P_n$) contains $Q+P_n$ (respectively, $Q+n{K}_1$) as a subgraph; then we have $cr(Q+C_n)\ge cr(Q+P_n)\ge cr(Q+n{K}_1)$ for $n\ge 3.$

On the other hand, in Figure 5 and Figure 6 (when n is odd and even, respectively), we can add the edges which belong to path $P_n$ or cycle $C_n,$ to $Q+n{K}_1$ that without crossings increased; thus,

$$cr(Q+P_n)\le cr(Q+C_n)\le cr(Q+n{K}_1)=\left\{\begin{array}{cc}Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill & n\mathrm{is}\mathrm{an}\mathrm{even}\mathrm{number};\hfill \\ Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2,\hfill & n\mathrm{is}\mathrm{an}\mathrm{odd}\mathrm{number}.\hfill \end{array}\right.$$

Thus, $cr(Q+P_1)=0,$$cr(Q+P_2)=2,$ and for $n\ge 3,$ we have

$$cr(Q+P_n)=cr(Q+C_n)=\left\{\begin{array}{cc}Z(6,n)+2\lfloor \frac{n}{2}\rfloor ,\hfill & n\mathrm{is}\mathrm{an}\mathrm{even}\mathrm{number};\hfill \\ Z(6,n)+2\lfloor \frac{n}{2}\rfloor -2,\hfill & n\mathrm{is}\mathrm{an}\mathrm{odd}\mathrm{number}.\hfill \end{array}\right.$$

The proof is completed.  □