Michal Stasˇ

Department of Mathematics and Theoretical Informatics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Kosice, Slovak Republic ˇ

michal.stas@tuke.sk

The main aim of this paper is to give the crossing number of the join product G⇤ + Dⁿ for the disconnected graph G⇤ of order five consisting of the complete graph K⁴ and of one isolated vertex, and where Dⁿ consists of n isolated vertices. In the proofs, the idea of a minimum number of crossings between two different subgraphs by which the graph G⇤ is crossed exactly once will be extended. All methods used in the paper are new, and they are based on combinatorial properties of cyclic permutations. Finally, by adding new edges to the graph G⇤, we are able to obtain the crossing numbers of Gⁱ + Dⁿ for two other graphs Gⁱ of order five.

Keywords: graph, drawing, crossing number, join product, cyclic permutation Mathematics Subject Classification : 05C10, 05C38

DOI: 10.5614/ejgta.2020.8.2.10

1. Introduction

Over the last years, some results concerning crossing numbers of join products of two graphs have been obtained. It is well known that the problem of reducing the number of crossings on the edges in the drawings of graphs was studied in many areas, and the most prominent area is VLSI technology. The lower bound on the chip area is determined by the crossing number and by the number of vertices of the graph. By Garey and Johnson [4] we already know that the computing of the crossing number of a given graph in general is NP-complete problem.

Received: 14 October 2018, Revised: 18 July 2020, Accepted: 23 September 2020.

The crossing number cr(G) of a simple graph G with the vertex set V (G) and the edge set E(G) is the minimum possible number of edge crossings in a drawing of G in the plane. (For the definition of a drawing see [9].) It is easy to see that a drawing with minimum number of crossings (an optimal drawing) is always a good drawing, meaning that no edge crosses itself, no two edges cross more than once, and no two edges incident with the same vertex cross. Let D (D(G)) be a good drawing of the graph G. We denote the number of crossings in D by crD(G). Let Gⁱ and G^j be edge-disjoint subgraphs of G. We denote the number of crossings between edges of Gⁱ and edges of G^j by crD(Gi, G^j ), and the number of crossings among edges of Gⁱ in D by crD(Gi). It is easy to see that for any three mutually edge-disjoint subgraphs Gi, G^j , and G^k of G, the following equations hold:

\[\operatorname{cr}_D(G_i \cup G_j) = \operatorname{cr}_D(G_i) + \operatorname{cr}_D(G_j) + \operatorname{cr}_D(G_i, G_j),\]
\[\operatorname{cr}_D(G_i \cup G_j, G_k) = \operatorname{cr}_D(G_i, G_k) + \operatorname{cr}_D(G_j, G_k).\]

In the paper, some proofs will be also based on the Kleitman's result on crossing numbers of the complete bipartite graphs [7]. More precisely, he proved that

\[\operatorname{cr}(K_{m,n}) = \left\lfloor \frac{m}{2} \right\rfloor \left\lfloor \frac{m-1}{2} \right\rfloor \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor, \quad \text{if} \quad \min\{m,n\} \le 6.\]

The exact values for the crossing numbers of G + Dⁿ for all graphs G of order at most four are given by Klesˇc and Schr ˇ otter [12]. Also, the crossing numbers of the graphs ¨ G + Dⁿ are known for few graphs G of order five and six, see [3], [8], [9], [10], [11], and [16]. In all these cases, the graph G is connected and contains at least one cycle. The crossing numbers of the join product G + Dⁿ are known only for some disconnected graphs G, and so the purpose of this article is to extend the known results concerning this topic to new disconnected graphs, see [2] and [15].

The methods used in the paper are new, and they are based on combinatorial properties of the cyclic permutations. In [2] and [3] by Bereznˇ y and Sta ´ s, the properties of cyclic permutations are ˇ also verified by the help of software. Also in this article, some parts of proofs can be simplified by utilizing the work of the software COGA that generates all cyclic permutations by Bereznˇ y´ and Busa [1]. The similar methods were partially used earlier in the papers [6] and [14]. We were ˇ unable to determine the crossing number of the join product G⇤+Dⁿ using the methods used in [9], [11], and [12]. Let G⇤ be the disconnected graph of order five consisting of one isolated vertex and of the complete graph K4, and let V (G⇤) = {v1, v2,...,v5}. We consider the join product of G⇤ with the discrete graph on n vertices denoted by Dⁿ Clearly, the graph G⇤ + Dⁿ consists of one copy of the graph G⇤ and of n vertices t1, t2,...,tn, where any vertex ti, i = 1, 2,...,n, is adjacent to every vertex of G⇤. Let Tⁱ , i = 1,...,n, denote the subgraph induced by the five edges incident with the vertex ti. This means that the graph T¹ [ ··· [ T ⁿ is isomorphic with the complete bipartite graph K5,n and therefore, we can write

\[G^* + D_n = G^* \cup K_{5,n} = G^* \cup \left(\bigcup_{i=1}^n T^i\right).\]

2. Cyclic permutations, configurations, and possible drawings of \(G^*\)

Let D be a good drawing of the graph \(G^* + D_n\). The rotation \(\operatorname{rot}_D(t_i)\) of a vertex \(t_i\) in the drawing D is the cyclic permutation that records the (cyclic) counter-clockwise order in which the edges leave \(t_i\), see [6]. We use the notation (12345) if the counter-clockwise order the edges incident with the vertex \(t_i\) is \(t_iv_1, t_iv_2, t_iv_3, t_iv_4\), and \(t_iv_5\). We emphasize that a rotation is a cyclic permutation; that is, (12345), (23451), (34512), (45123), and (51234) denote the same rotation. Thus, 5!/5 = 24 different \(\operatorname{rot}_D(t_i)\) can appear in a drawing of the graph \(G^* + D_n\). By \(\overline{\operatorname{rot}}_D(t_i)\) we understand the inverse permutation of \(\operatorname{rot}_D(t_i)\). In the given drawing D, we separate all subgraphs \(T^i\), \(i=1,\ldots,n\), of the graph \(G^* + D_n\) into three mutually disjoint subsets depending on how many times the considered \(T^i\) crosses the edges of \(G^*\) in D. For \(i=1,\ldots,n\), \(T^i \in R_D\) if \((G^*,T^i)=0\) and \(T^i \in S_D\) if \(\operatorname{cr}_D(G^*,T^i)=1\). Every other subgraph \(T^i\) crosses the edges of \(G^*\) at least twice in D. Due to arguments in the proof of Theorem 3.1, at least one of the sets \(R_D\) and \(S_D\) must be nonempty in a good drawing D of \(G^* + D_n\) with the smallest number of crossings. For \(T^i \in R_D \cup S_D\), let \(F^i\) denote the subgraph \(G^* \cup T^i\), \(i \in \{1,2,\ldots,n\}\), of \(G^* + D_n\) and let \(D(F^i)\) be its subdrawing induced by D.

Let us discuss all possible drawings of \(G^*\). Since the graph \(G^*\) contains \(K_4\) as a subgraph (for brevity, we write \(K_4(G^*)\)), we only need to consider possibilities of crossings among edges of \(K_4(G^*)\). If we suppose a good subdrawing of \(G^*\) in which the edges of \(K_4(G^*)\) do not cross each other, then the isolated vertex of \(G^*\) can be placed in arbitrary triangular region of \(D(K_4(G^*))\) and we always obtain the same drawing with respect to isomorphisms that is shown in Figure 1(a). If the edges of \(K_4(G^*)\) cross each other, then there are next two possibilities depending on in which region of \(D(K_4(G^*))\) the isolated vertex of \(G^*\) is placed and they are shown in Figure 1(b), and (c). The vertex notation of the graph \(G^*\) in Figure 1 will be justified later.

Figure 1. One planar drawing of \(G^*\) and two drawings of \(G^*\) with \(\operatorname{cr}_D(G^*)=1\).

First, let us assume a good drawing D of the graph \(G^* + D_n\) in which the edges of \(G^*\) do not cross each other. In this case, without loss of generality, we can choose the vertex notation of the graph \(G^*\) in such a way as shown in Figure 1(a). It is obvious that the set \(R_D\) is empty, and so our aim is to list all possible rotations \(\operatorname{rot}_D(t_i)\) which can appear in D if the edges of \(T^i\) cross the edges of \(G^*\) exactly once. Since there is only one subdrawing of \(F^i \setminus \{v_3, v_5\}\) represented by the rotation (142), there are three possibilities how to obtain the subdrawing of \(F^i \setminus v_5\) depending on which edge of the graph \(G^*\) is crossed by the edge \(t_iv_3\). Every of these three subdrawings of \(F^i \setminus v_5\) produces four drawings of \(F^i\) depending on in which region the edge \(t_iv_5\) is placed. We denote these twelve possibilities under our consideration by \(A_k\), and \(B_k\), for \(k = 1, \ldots, 6\). The

configuration is of type \(\mathcal{A}\) or \(\mathcal{B}\), if the vertex \(v_5\) is placed in the triangular region with two vertices or with one vertex of \(G^*\) on its boundary in the subdrawing \(D(F^i \setminus v_5)\), respectively. In the rest of the paper, each cyclic permutation is represented by the permutation with 1 in the first position. Thus, the configurations \(\mathcal{A}_1\), \(\mathcal{A}_2\), \(\mathcal{A}_3\), \(\mathcal{A}_4\), \(\mathcal{A}_5\), \(\mathcal{A}_6\), \(\mathcal{B}_1\), \(\mathcal{B}_2\), \(\mathcal{B}_3\), \(\mathcal{B}_4\), \(\mathcal{B}_5\), and \(\mathcal{B}_6\) are represented by the cyclic permutations (14325), (14523), (15423), (13425), (13452), (15432), (15342), (14532), (14253), and (14235), respectively. Of course, in a fixed drawing of the graph \(G^* + D_n\), some configurations from \(\mathcal{M} = \{\mathcal{A}_1, \mathcal{A}_2, \mathcal{A}_3, \mathcal{A}_4, \mathcal{A}_5, \mathcal{A}_6, \mathcal{B}_1, \mathcal{B}_2, \mathcal{B}_3, \mathcal{B}_4, \mathcal{B}_5, \mathcal{B}_6\}\) need not appear. So we denote by \(\mathcal{M}_D\) the set of all configurations of \(\mathcal{M}\) that appear in D.

Now, we deal with the minimum numbers of crossings between two different subgraphs \(T^i\)and \(T^j\) depending on the configurations of subgraphs \(F^i\) and \(F^j\). Let D be a good drawing of the graph \(G^* + D_n\), and let \(\mathcal{X}, \mathcal{Y}\) be configurations from \(\mathcal{M}_D\). We shortly denote by \(\operatorname{cr}_D(\mathcal{X}, \mathcal{Y})\)the number of crossings in D between \(T^i\) and \(T^j\) for different \(T^i, T^j \in S_D\) such that \(F^i, F^j\) have configurations \(\mathcal{X}\), \(\mathcal{Y}\), respectively. Finally, let \(\operatorname{cr}(\mathcal{X}, \mathcal{Y}) = \min\{\operatorname{cr}_D(\mathcal{X}, \mathcal{Y})\}\\) over all pairs \(\mathcal{X}\) and \(\mathcal{Y}\) from \(\mathcal{M}\) among all good drawings of the graph \(G^* + D_n\). Our aim is to establish \(\operatorname{cr}(\mathcal{X}, \mathcal{Y})\) for all pairs \(\mathcal{X}, \mathcal{Y} \in \mathcal{M}\). In particular, the configurations \(\mathcal{A}_1\) and \(\mathcal{A}_2\) are represented by the cyclic permutations (14325) and (14523), respectively. Since the minimum number of interchanges of adjacent elements of (14325) required to produce cyclic permutation (14523) = (13254) is one, any subgraph \(T^j\) with the configuration \(\mathcal{A}_2\) of \(F^j\) crosses the edges of \(T^i\) with the configuration \(\mathcal{A}_1\)of \(F^i\) at least once¹, i.e., \(cr(A_1, A_2) \ge 1\). The same reason gives \(cr(A_3, A_4) \ge 1\), \(cr(A_5, A_6) \ge 1\), \(\operatorname{cr}(\mathcal{A}_1, \mathcal{A}_3) \geq 2, \operatorname{cr}(\mathcal{A}_1, \mathcal{A}_5) \geq 2, \operatorname{cr}(\mathcal{A}_3, \mathcal{A}_5) \geq 2, \operatorname{cr}(\mathcal{A}_2, \mathcal{A}_4) \geq 2, \operatorname{cr}(\mathcal{A}_2, \mathcal{A}_6) \geq 2, \operatorname{cr}(\mathcal{A}_4, \mathcal{A}_6) \geq 2\)\(2, \operatorname{cr}(A_1, B_3) \ge 2, \operatorname{cr}(A_1, B_5) \ge 2, \operatorname{cr}(A_3, B_1) \ge 2, \operatorname{cr}(A_3, B_5) \ge 2, \operatorname{cr}(A_5, B_1) \ge 2, \operatorname{cr}(A_5, B_3) \ge 2\)\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)\(\operatorname{cr}(\mathcal{A}_6, \mathcal{B}_4) \geq 2\). Moreover, the Woodall's result for m=5 also implies that \(\operatorname{cr}(\mathcal{A}_n, \mathcal{B}_n) \geq 4\)holds for any p = 1, ..., 6, and \(\operatorname{cr}(\mathcal{B}_p, \mathcal{B}_q) \ge 4\) holds with respect to the restrictions \(p \equiv q \pmod{2}\), where p, q = 1, ..., 6. Clearly, also \(cr(\mathcal{A}_p, \mathcal{A}_p) \ge 4\) for any p = 1, ..., 6. For all remaining pairs of configurations are established the minimum numbers of crossings at least three. For any \(T^i \in S_D\)with the configuration \(\mathcal{B}_1\) of \(F^i\), if there is a subgraph \(T^j \in S_D\), \(j \neq i\) such that \(\operatorname{cr}_D(T^i, T^j) \leq\)2, then the vertex \(t_j\) must be placed in the triangular region with two vertices \(v_1\), \(v_2\) or in the quadrangular region with two vertices \(v_1\), \(v_5\) of \(G^*\) on its boundary in the subdrawing \(D(F^i)\). Hence, the subgraph \(F^j\) is exactly represented by \(rot_D(t_i) = (15423)\) or \(rot_D(t_i) = (13452)\), and therefore, \(\operatorname{cr}(\mathcal{B}_1, \mathcal{A}_p) \geq 3\) and \(\operatorname{cr}(\mathcal{B}_1, \mathcal{B}_p) \geq 3\) hold for each p = 2, 4, 6. Similar arguments can be applied for the configurations \(\mathcal{B}_q\) of some subgraph \(F^i\) for \(q=2,\ldots,6\). The resulting lower bounds for the number of crossings of configurations from \(\mathcal{M}\) are summarized in the symmetric Table 1. (Here, \(\mathcal{X}_p\) and \(\mathcal{Y}_q\) are configurations of the subgraphs \(F^i\) and \(F^j\), where \(p, q \in \{1, \dots, 6\}\)and \(\mathcal{X}, \mathcal{Y} \in \{\mathcal{A}, \mathcal{B}\}\).)

Assume a good drawing D of the graph \(G^* + D_n\) in which the edges of \(G^*\) cross each other exactly once and the isolated vertex of the graph \(G^*\) is placed in the quadrangular region in the

^&lt;sup>1</sup>Let \(T^i\) and \(T^j\) be two different subgraphs represented by their \(\operatorname{rot}(t_i)\) and \(\operatorname{rot}(t_j)\) of length \(m, m \geq 3\). If we define \(Q(\operatorname{rot}_D(t_i), \operatorname{rot}_D(t_j))\) as the minimum number of interchanges of adjacent elements of \(\operatorname{rot}_D(t_i)\) required to produce the inverse cyclic permutation of \(\operatorname{rot}_D(t_j)\) or, equivalently, from \(\operatorname{rot}_D(t_j)\) to the inverse of \(\operatorname{rot}_D(t_i)\), then \(\operatorname{cr}_D(T^i, T^j) \geq Q(\operatorname{rot}_D(t_i), \operatorname{rot}_D(t_j))\). For m odd, \(\operatorname{cr}_D(T^i, T^j) = Q(\operatorname{rot}_D(t_i), \operatorname{rot}_D(t_j)) + 2k\) is fulfilling for some nonnegative integer k. Details have been worked out by Woodall [17].

Table 1. The necessary number of crossings between \(T^i\) and \(T^j\) for the configurations \(\mathcal{X}_p\), \(\mathcal{Y}_q\).

subdrawing \(D(G^* \setminus v_5)\). In this case, without loss of generality, we can choose the vertex notation of the graph \(G^*\) in such a way as shown in Figure 1(c). It is not difficult to verify that there is no subgraph \(T^i\) by which the edges of \(G^*\) are crossed exactly once, i.e., the set \(S_D\) is empty, and so our aim is to list all possible rotations \(\operatorname{rot}_D(t_i)\) which can appear in D if the edges of \(T^i\) do not cross the edges of \(G^*\). Since there is only one subdrawing of \(F^i \setminus v_5\) represented by the rotation (1432), we have four possibilities how to obtain the subdrawing of \(F^i\) depending on in which region the vertex \(v_5\) is placed. Thus, there are four different possible configurations of the subgraph \(F^i\) denoted as \(\mathcal{E}_1\), \(\mathcal{E}_2\), \(\mathcal{E}_3\), and \(\mathcal{E}_4\), i.e., \(\operatorname{rot}_D(t_i) = \mathcal{E}_p\) for p = 1, 2, 3, 4, and they are represented by the cyclic permutations (14325), (14352), (14352), and (15432), respectively. As for our considerations does not play role which of the regions is unbounded, assume the drawings shown in Figure 2.

Figure 2. Four drawings of possible configurations from \(\mathcal{N}\) of subgraph \(F^i\).

Also, in a fixed drawing of the graph \(G^* + D_n\), some configurations from \(\mathcal{N} = \{\mathcal{E}_1, \mathcal{E}_2, \mathcal{E}_3, \mathcal{E}_4\}\) need not appear. We denote by \(\mathcal{N}_D\) the set of all configurations that exist in the drawing D belonging to the set \(\mathcal{N}\). The verification of the lower bounds for number of crossings of two configurations from \(\mathcal{N}\) proceeds in the same way like above. Thus, all lower bounds of number of crossings of

configurations from \(\mathcal{N}\) are summarized in Table 2. (Here, \(\mathcal{E}_p\) and \(\mathcal{E}_q\) are configurations of the subgraphs \(F^i\) and \(F^j\), where \(p, q \in \{1, 2, 3, 4\}\).)

Table 2. The necessary number of crossings between \(T^i\) and \(T^j\) for the configurations \(\mathcal{E}_p\), \(\mathcal{E}_q\).

3. The crossing number of \(G^* + D_n\)

Two vertices \(t_i\) and \(t_j\) of the graph \(G^* + D_n\) are antipodal in a drawing of \(G^* + D_n\) if the subgraphs \(T^i\) and \(T^j\) do not cross. A drawing is antipode-free if it has no antipodal vertices. Now we are able to prove the main result of this paper.

Figure 3. The good drawing of \(G^* + D_n\) with \(4\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor + n + \lfloor \frac{n}{2} \rfloor\) crossings.

Theorem 3.1. \[\operatorname{cr}(G^* + D_n) = 4 \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor + n + \lfloor \frac{n}{2} \rfloor\] for \(n \geq 1\).

Proof. In Figure 3 there is the drawing of the graph \(G^* + D_n\) with \(4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor\) crossings. Thus, \(\operatorname{cr}(G^* + D_n) \leq 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor\). We prove the reverse inequality by induction on n. The graph \(G^* + D_1\) contains \(K_5\) as a subgraph and the graph \(G^* + D_2\) is a subdivision of \(K_6\). It was proved in [5] that \(\operatorname{cr}(K_5) = 1\) and \(\operatorname{cr}(K_6) = 3\). So, the result is true for n = 1 and n = 2. Suppose now that, for some \(n \geq 3\), there is a drawing D with

\[\operatorname{cr}_{D}(G^{*} + D_{n}) < 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor, \tag{1}\]

and that

\[\operatorname{cr}(G^* + D_m) = 4\left\lfloor \frac{m}{2} \right\rfloor \left\lfloor \frac{m-1}{2} \right\rfloor + m + \left\lfloor \frac{m}{2} \right\rfloor\] for any positive integer \(m < n\). (2)

Our assumption on D together with \(\operatorname{cr}(K_{5,n}) = 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor\) implies that

\[\operatorname{cr}_D(G^*) + \operatorname{cr}_D(G^*, K_{5,n}) < n + \left\lfloor \frac{n}{2} \right\rfloor.\]

Moreover, if \(r = |R_D|\) and the set \(S_D\) is empty, then

\[\operatorname{cr}_D(G^*) + 0r + 2(n-r) < n + \left| \frac{n}{2} \right|,\] (3)

which forces \(r \ge \frac{\left\lceil \frac{n}{2} \right\rceil + 1 + \operatorname{cr}_D(G^*)}{2}\). In the case, if \(s = |S_D|\) and the set \(R_D\) is empty, then

\[\operatorname{cr}_{D}(G^{*}) + 1s + 2(n-s) < n + \left\lfloor \frac{n}{2} \right\rfloor, \tag{4}\]

which implies \(s \ge \left\lceil \frac{n}{2} \right\rceil + 1 + \operatorname{cr}_D(G^*)\). Now, for \(T^i \in R_D \cup S_D\), we discuss the existence of possible configurations of subgraph \(F^i = G^* \cup T^i\) in the drawing D and we show that in all cases a contradiction with the assumption (1) is obtained.

Case 1: \(\operatorname{cr}_D(G^*) = 0\). Without loss of generality, we can choose the vertex notation of the graph \(G^*\) in such a way as shown in Figure 1(a). Since the set \(R_D\) is empty, we deal with the configurations belonging to the nonempty set \(\mathcal{M}_D\) according to inequality (4).

We claim that the considered drawing D must be antipode-free. Of course, if \(T^k\) and \(T^l\) are two different subgraphs from the nonempty set \(S_D\), then the vertices \(v_k\) and \(v_l\) are not antipodal due to the positive values in Table 1. For a contradiction, suppose that \(\operatorname{cr}_D(T^k, T^l) = 0\), and at least one of the subgraphs \(T^k\) and \(T^l\) is not included in the set \(S_D\), which yields that \(\operatorname{cr}_D(G^*, T^k \cup T^l) \geq 3\). Moreover, the known fact that \(\operatorname{cr}(K_{5,3}) = 4\) implies that each \(T^m\), \(m \neq k, l\), crosses the edges of the subgraph \(T^k \cup T^l\) at least four times. So, for the number of crossings in D we have

\[\operatorname{cr}_D(G^* + D_n) = \operatorname{cr}_D(G^* + D_{n-2}) + \operatorname{cr}_D(T^k \cup T^l) + \operatorname{cr}_D(K_{5,n-2}, T^k \cup T^l) + \operatorname{cr}_D(G^*, T^k \cup T^l)\]

\[\geq 4\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor+n-2+\left\lfloor\frac{n-2}{2}\right\rfloor+0+4(n-2)+3=4\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor+n+\left\lfloor\frac{n}{2}\right\rfloor.\]

This contradiction with the assumption (1) confirms that D is antipode-free. For \(T^i \in S_D\), we deal with the configurations belonging to the set \(\mathcal{M}_D\) and we discuss over all possible subsets of \(\mathcal{M}_D\) in the following subcases:

a) \(\{\mathcal{A}_o, \mathcal{A}_{o+1}\}\subseteq \mathcal{M}_D\) for some \(o\in\{1,3,5\}\). Without lost of generality, let us consider two different subgraphs \(T^{n-1}\), \(T^n\in S_D\) such that \(F^{n-1}\) and \(F^n\) have configurations \(\mathcal{A}_1\) and \(\mathcal{A}_2\), respectively. Then, \(\operatorname{cr}_D(T^{n-1}\cup T^n,T^k)\geq 5\) is fulfilling for any \(T^k\in S_D\) with \(k\neq n-1,n\) by summing the values in all columns in the first two rows of Table 1. Moreover, \(\operatorname{cr}_D(T^{n-1}\cup T^n,T^k)\geq 3\) holds for any \(T^k\not\in S_D\) provided by the minimum number of interchanges of adjacent elements of \(\operatorname{rot}_D(t_{n-1})\) required to produce the cyclic permutation \(\operatorname{rot}_D(t_n)\) is three. As \(\operatorname{cr}_D(G^*\cup T^{n-1}\cup T^n)\geq 3\), by fixing the graph \(T^{n-1}\cup T^n\), we have

\[\operatorname{cr}_D(G^* + D_n) \ge 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + n - 2 + \left\lfloor \frac{n-2}{2} \right\rfloor + 1 + 5(s-2) + 3(n-s) + 2\]

On the crossing number of join product of the discrete graph ... | Michal Staš

\[=4\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor+\left\lfloor\frac{n-2}{2}\right\rfloor+4n+2s-9\geq 4\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor+\left\lfloor\frac{n-2}{2}\right\rfloor\\+4n+2\left(\left\lceil\frac{n}{2}\right\rceil+1\right)-9\geq 4\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor+n+\left\lfloor\frac{n}{2}\right\rfloor.\]

This contradicts the assumption of D. Due to the symmetry, the same arguments are applied for the cases \(\{A_3, A_4\}\) and \(\{A_5, A_6\}\).

b) \(\{\mathcal{A}_o, \mathcal{A}_{o+1}\} \not\subseteq \mathcal{M}_D\) for o=1,3,5. Let us first suppose that \(\{\mathcal{A}_p, \mathcal{A}_{p+2}, \mathcal{A}_{p+4}\} \subseteq \mathcal{M}_D\) for some \(p \in \{1,2\}\) or there are three mutually different \(o,p,q \in \{1,\dots,6\}\) with \(o \equiv p \equiv q \pmod{2}\) such that \(\{\mathcal{A}_o, \mathcal{A}_p, \mathcal{B}_q\} \subseteq \mathcal{M}_D\). Without lost of generality, let us consider three different subgraphs \(T^{n-2}\), \(T^{n-1}\), \(T^n \in S_D\) such that \(F^{n-2}\), \(F^{n-1}\) and \(F^n\) have configurations \(\mathcal{A}_1\), \(\mathcal{A}_3\) and \(\mathcal{B}_5\), respectively. Then, \(\operatorname{cr}_D(T^{n-2} \cup T^{n-1} \cup T^n, T^k) \geq 8\) holds for any \(T^k \in S_D\) with \(k \neq n-2, n-1, n\) by summing of three corresponding values of Table 1. Moreover, if there is a subgraph \(T^k\), \(k \neq n-1, n\) such that \(\operatorname{cr}_D(T^{n-1} \cup T^n, T^k) = 2\), then the minimum number of interchanges of adjacent elements of \(\operatorname{rot}_D(t_{n-2})\) required to produce the inverse cyclic permutation of \(\operatorname{rot}_D(t_k)\) is at least two, and so \(\operatorname{cr}_D(T^{n-2} \cup T^{n-1} \cup T^n, T^k) \geq 4\) holds for any \(T^k \notin S_D\). As \(\operatorname{cr}_D(T^{n-2} \cup T^{n-1} \cup T^n) \geq 6\), by fixing the graph \(T^{n-2} \cup T^{n-1} \cup T^n\), we have

\[\operatorname{cr}_{D}(G^{*} + D_{n}) \geq 4 \left\lfloor \frac{n-3}{2} \right\rfloor \left\lfloor \frac{n-4}{2} \right\rfloor + n - 3 + \left\lfloor \frac{n-3}{2} \right\rfloor + 8(s-3) + 4(n-s) + 6 + 3\] \[= 4 \left\lfloor \frac{n-3}{2} \right\rfloor \left\lfloor \frac{n-4}{2} \right\rfloor + \left\lfloor \frac{n-3}{2} \right\rfloor + 5n + 4s - 18 \geq 4 \left\lfloor \frac{n-3}{2} \right\rfloor \left\lfloor \frac{n-4}{2} \right\rfloor + \left\lfloor \frac{n-3}{2} \right\rfloor\] \[+5n + 4 \left( \left\lceil \frac{n}{2} \right\rceil + 1 \right) - 18 \geq 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

This also contradicts the assumption of D. The verification for all seven other possibilities proceeds in the same way and therefore, in the next part, suppose that \(\{\mathcal{A}_p, \mathcal{A}_{p+2}, \mathcal{A}_{p+4}\} \not\subseteq \mathcal{M}_D\) for any p=1,2, and also \(\{\mathcal{A}_o, \mathcal{A}_p, \mathcal{B}_q\} \not\subseteq \mathcal{M}_D\) with \(o\equiv p\equiv q \pmod 2\) for any three mutually different \(o,p,q=1,\ldots,6\). Now, for \(T^i\in S_D\), we will discuss the possibility of obtaining a subdrawing of \(G^*\cup T^i\cup T^j\) in D with \(\operatorname{cr}_D(T^i,T^j)=2\) for some \(T^j\in S_D\).

Let us consider that there are two subgraphs \(T^i\), \(T^j \in S_D\) with \(\operatorname{cr}_D(T^i, T^j) = 2\) such that \(F^i\) and \(F^j\) have configurations \(\mathcal{X}_p\) and \(\mathcal{Y}_q\), respectively, where \(\mathcal{X}, \mathcal{Y} \in \{\mathcal{A}, \mathcal{B}\}\) and \(p,q \in \{1,\ldots,6\}\). Then, \(\operatorname{cr}_D(T^i \cup T^j, T^k) \geq 6\) holds for any \(T^k \in S_D\), \(k \neq i,j\) by summing of two corresponding values of Table 1. Thus, by fixing the graph \(T^{n-1} \cup T^n\), we have

\[\operatorname{cr}_{D}(G^{*} + D_{n}) \geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + n - 2 + \left\lfloor \frac{n-2}{2} \right\rfloor + 6(s-2) + 2(n-s) + 2 + 2\] \[= 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + \left\lfloor \frac{n-2}{2} \right\rfloor + 3n + 4s - 10 \geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + \left\lfloor \frac{n-2}{2} \right\rfloor\] \[+3n + 4 \left( \left\lceil \frac{n}{2} \right\rceil + 1 \right) - 10 \geq 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

Finally, assume that there are no two different \(T^i, T^j \in S_D\) with \(\operatorname{cr}_D(T^i, T^j) \leq 2\). Hence, for each \(T^i \in S_D\), \(\operatorname{cr}_D(G^* \cup T^i, T^k) \geq 1 + 3 = 4\) is fulfilling for any \(T^k \in S_D\) with \(k \neq i\) and \(\operatorname{cr}_D(G^* \cup T^i, T^k) \geq 2 + 1 = 3\) is also true for any \(T^k \notin S_D\). Consequently, by fixing the graph \(G^* \cup T^i\), we have

\[\operatorname{cr}_{D}(G^{*} + D_{n}) = \operatorname{cr}_{D}(K_{5,n-1}) + \operatorname{cr}_{D}(K_{5,n-1}, G^{*} \cup T^{i}) + \operatorname{cr}_{D}(G^{*} \cup T^{i})\] \[\geq 4 \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor + 4(s-1) + 3(n-s) + 1 = 4 \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor + 3n + s - 3\] \[\geq 4 \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor + 3n + \left( \left\lceil \frac{n}{2} \right\rceil + 1 \right) - 3 \geq 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

Case 2: \(\operatorname{cr}_D(G^*)=1\) and we consider the drawing of \(G^*\) with the vertex notation like that in Figure 1(b). It is obvious that the set \(R_D\) is empty, and so there are at least \(\left\lceil \frac{n}{2} \right\rceil + 2\) subgraphs \(T^i\) by which the edges of \(G^*\) are crossed exactly once. For \(T^i \in S_D\), the subgraph \(F^i\) is represented by \(\operatorname{rot}_D(t_i)=(14325)\), which yields that \(\operatorname{cr}_D(T^i,T^j)\geq 4\) is fulfilling for any \(T^j\in S_D\) with \(j\neq i\) provided that \(\operatorname{rot}_D(t_i)=\operatorname{rot}_D(t_j)\). By fixing the graph \(T^i\), we have

\[\operatorname{cr}_{D}(G^{*}+D_{n}) \geq 4\left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor + n - 1 + \left\lfloor \frac{n-1}{2} \right\rfloor + 4(s-1) + 1\] \[\geq 4\left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor + \left\lfloor \frac{n-1}{2} \right\rfloor + n + 4\left( \left\lceil \frac{n}{2} \right\rceil + 2 \right) - 4 \geq 4\left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

Case 3: \(\operatorname{cr}_D(G^*)=1\) and we consider the drawing of \(G^*\) with the vertex notation like that in Figure 1(c). Since the set \(S_D\) is empty, we deal with the configurations belonging to the nonempty set \(\mathcal{N}_D\). Again, we claim that the drawing D must be antipode-free. For a contradiction, suppose that \(\operatorname{cr}_D(T^k,T^l)=0\). If at least one of \(T^k\) and \(T^l\), say \(T^k\), does not cross \(G^*\), it is not difficult to verify that \(T^l\) must cross \(G^* \cup T^k\) at least thrice, that is, \(\operatorname{cr}_D(G^*,T^k \cup T^l)\geq 3\). Consequently, the same arguments like in Case 1 confirm that D is antipode-free. Now, we consider the following subcases:

a) \(\{\mathcal{E}_p,\mathcal{E}_{p+1}\}\subseteq\mathcal{N}_D\) for some \(p\in\{1,3\}\). Without lost of generality, let us consider two different subgraphs \(T^{n-1}\), \(T^n\in R_D\) such that \(F^{n-1}\) and \(F^n\) have configurations \(\mathcal{E}_1\) and \(\mathcal{E}_2\), respectively. As the considered drawing D is antipode-free, each \(T^k\), \(k\neq n-1, n\) crosses the edges of the subgraph \(T^{n-1}\cup T^n\) at least twice, and \(\mathrm{cr}_D(T^{n-1}\cup T^n,T^k)\geq 2\) holds with equality only when \(\mathrm{cr}_D(T^{n-1},T^k)=1\) and \(\mathrm{cr}_D(T^n,T^k)=1\). This enforces that a such subgraph \(T^k\) crosses the edges of \(G^*\) at least thrice, otherwise, \(\mathrm{rot}_D(t_k)\in\{(15324),(14523)\}\) and \(\mathrm{rot}_D(t_k)\in\{(13254),(14235)\}\) if \(\mathrm{cr}_D(T^{n-1},T^k)=1\) and \(\mathrm{cr}_D(T^n,T^k)=1\), respectively. This impossibility of the same rotation of the vertex \(t_k\) implies \(\mathrm{cr}_D(G^*,T^k)\geq 3\). Thus, let us denote \(L_D(T^{n-1},T^n)=\{T^k:\mathrm{cr}_D(T^{n-1}\cup T^n,T^k)=2 \text{ and }\mathrm{cr}_D(G^*,T^k)=3\}\), and \(l=|L_D(T^{n-1},T^n)|\). If suppose the case \(\mathrm{cr}_D(G^*,T^k)\geq 3\) if \(\mathrm{cr}_D(T^n,T^k)=1\) and \(\mathrm{cr}_D(T^{n-1},T^k)=1\), respectively, that is, \(\mathrm{cr}_D(G^*\cup T^{n-1}\cup T^n,T^k)=5\) is fulfilling only for the subgraphs \(T^k\in L_D(T^{n-1},T^n)\). Hence, we discuss two possibilities:

1) Suppose that \(l < \lfloor \frac{n+1}{2} \rfloor\), that is, \(-l \ge 1 - \lfloor \frac{n+1}{2} \rfloor\). Also, by summing the values in all columns in the first two rows of Table 2, \(\operatorname{cr}_D(T^{n-1} \cup T^n, T^k) \ge 6\) holds for any \(T^k \in R_D\) with \(k \ne n-1, n\). Thus, by fixing the graph \(G^* \cup T^{n-1} \cup T^n\), we have

\[\operatorname{cr}_{D}(G^{*}+D_{n}) \geq 4\left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 6(r-2) + 5l + 6(n-r-l) + 2 + 1\] \[\geq 4\left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 6n + \left(1 - \left\lfloor \frac{n+1}{2} \right\rfloor\right) - 9 \geq 4\left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

2) Suppose that \(l \geq \lfloor \frac{n+1}{2} \rfloor\), that is, \(-2l \leq -2 \lfloor \frac{n+1}{2} \rfloor\). Let us denote by H the subgraph of \(G^*\) with the vertex set \(V(G^*)\) and the edge set \(E(G^*) \setminus \{v_1v_3, v_2v_4\}\). Since the edges of any subgraph \(T^k \in L_D(T^{n-1}, T^n)\) cross both edges \(v_1v_3\) and \(v_2v_4\) once, then

\[\operatorname{cr}_{D}(H+D_{n}) < 4\left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor - 2l\] \[\leq 4\left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor - 2\left\lfloor \frac{n+1}{2} \right\rfloor \leq 4\left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + \left\lfloor \frac{n}{2} \right\rfloor.\]

This forces a contradiction with \(\operatorname{cr}(H+D_n)=4\left|\frac{n}{2}\right|\left|\frac{n-1}{2}\right|+\left|\frac{n}{2}\right|\), see [14].

Both subcases confirm a contradiction with the assumption in D, and therefore, suppose that \(\{\mathcal{E}_1, \mathcal{E}_2\} \not\subseteq \mathcal{N}_D\) and \(\{\mathcal{E}_3, \mathcal{E}_4\} \not\subseteq \mathcal{N}_D\) in all following cases.

• b) \(\mathcal{N}_D=\{\mathcal{E}_p,\mathcal{E}_q\}\) for two different p,q=1,2,3,4 with respect to the restriction 3< p+q<7. Without lost of generality, let us consider two different subgraphs \(T^{n-1},\ T^n\in R_D\) such that \(F^{n-1}\) and \(F^n\) have configurations \(\mathcal{E}_1\) and \(\mathcal{E}_3\), respectively. Since the minimum number of interchanges of adjacent elements of (14325) required to produce (14352) is one, each \(T^k,\ k\neq n-1,n\) crosses the edges of the subgraph \(T^{n-1}\cup T^n\) at least once, that is, \(\mathrm{cr}_D(T^{n-1}\cup T^n,T^k)\geq 1+2=3\) due to the Woodall's result [17]. Further, if there is a subgraph \(T^k,\ k\neq n-1,n\) such that \(\mathrm{cr}_D(T^{n-1}\cup T^n,T^k)=3\) then \(\mathrm{cr}_D(G^*,T^k)\geq 2\). Thus, let us denote \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\), and \(l=|L_D(T^{n-1},T^n)|\). Remark that \(\mathrm{cr}_D(G^*\cup T^{n-1}\cup T^n,T^k)=5\) is fulfilling only for subgraphs \(T^k\in L_D(T^{n-1},T^n)\). Hence, we discuss two possibilities:
  • 1) Suppose that \(l < 2\lfloor \frac{n+2}{4} \rfloor\), that is, \(-l \ge 1 2\lfloor \frac{n+2}{4} \rfloor\). Again, by summing of two corresponding values of Table 2, \(\operatorname{cr}_D(T^{n-1} \cup T^n, T^k) \ge 4 + 3 = 7\) holds for any \(T^k \in R_D\) with \(k \ne n-1, n\). Hence, by fixing the graph \(G^* \cup T^{n-1} \cup T^n\), we have

\[\operatorname{cr}_{D}(G^{*} + D_{n}) \geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 7(r-2) + 5l + 6(n-r-l) + 3 + 1\] \[\geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 6n + r - l - 10 \geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 6n\] \[+ \frac{\left\lceil \frac{n}{2} \right\rceil + 2}{2} + \left(1 - 2 \left\lfloor \frac{n+2}{4} \right\rfloor \right) - 10 \geq 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

2) Suppose that \(l \geq 2 \left \lfloor \frac{n+2}{4} \right \rfloor\). So, the inequality \(r+l \leq n\) forces \(-r \geq 2 \left \lfloor \frac{n+2}{4} \right \rfloor - n\). As \(\operatorname{cr}_D(T^{n-1} \cup T^n, T^k) = 3\) for each \(T^k \in L_D(T^{n-1}, T^n)\), there are at least \(\left \lceil \frac{l}{2} \right \rceil\) different subgraphs \(T^k\) such that \(\operatorname{cr}_D(T^{n-1}, T^k) = 1\) or \(\operatorname{cr}_D(T^n, T^k) = 1\). Further, it is not difficult to verify that if \(\operatorname{cr}_D(T^{n-1}, T^k) = 1\) or \(\operatorname{cr}_D(T^n, T^k) = 1\), then \(\operatorname{rot}_D(t_k) \in \{(15324), (14523)\}\) or \(\operatorname{rot}_D(t_k) \in \{(15342), (12543)\}\), respectively. Since the minimum number of interchanges of adjacent elements of (15324) required to produce \(\overline{(14523)} = (13254)\) is two, then \(\operatorname{cr}_D(T^{k_1}, T^{k_2}) \geq 2 + 2 = 4\) holds for any two subgraphs \(T^{k_1}, T^{k_2} \in L_D(T^{n-1}, T^n)\) with \(\operatorname{rot}_D(t_{k_1}) = (15324)\) and \(\operatorname{rot}_D(t_{k_2}) = (14523)\), see Woodall's result [17]. The same holds for the second pair of the rotations (15342) and (12543). Hence, for some \(i \in \{n-1,n\}\), \(\operatorname{cr}_D(G^* \cup T^i \cup T^k, T^j) \geq 2 + 1 + 4 = 7\) is fulfilling for any \(T^j \in L_D(T^{n-1}, T^n)\) with \(\operatorname{cr}_D(T^i, T^j) = 1\) and \(k \neq j\). By the antipode-free drawing D, \(\operatorname{cr}_D(G^* \cup T^i \cup T^k, T^j) \geq 2 + 2 + 1 = 5\) is also true for any \(T^j \in L_D(T^{n-1}, T^n)\) with \(\operatorname{cr}_D(T^i, T^j) = 2\). Thus, by fixing the graph \(G^* \cup T^i \cup T^k\), we have

\[\operatorname{cr}_{D}(G^{*} + D_{n}) \geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 5(r-1) + 7 \left( \left\lceil \frac{l}{2} \right\rceil - 1 \right) + 5 \left\lfloor \frac{l}{2} \right\rfloor\] \[+6(n-r-l) + 1 + 2 + 1 \geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 6n - r + 2 \left\lceil \frac{l}{2} \right\rceil - l - 8\] \[\geq 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 6n + 2 \left\lfloor \frac{n+2}{4} \right\rfloor - n - 8 \geq 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

Both subcases also contradict the assumption of D. Due to the symmetry, the proof proceeds in the similar way also for the remaining cases of two different configurations \(\{\mathcal{E}_1, \mathcal{E}_4\}\), \(\{\mathcal{E}_2, \mathcal{E}_3\}\), and \(\{\mathcal{E}_2, \mathcal{E}_4\}\).

• c) \(\mathcal{N}_D = \{\mathcal{E}_p\}\) for only one \(p \in \{1,2,3,4\}\). Without lost of generality, we can assume that \(T^n \in R_D\) with the configuration \(\mathcal{E}_1\) of the subgraph \(F^n\). Since there are still possibilities of obtaining a subgraph by which the edges of \(G^* \cup T^n\) are crossed thrice, let us denote \(L_D(T^n) = \{T^k : \operatorname{cr}_D(G^* \cup T^n, T^k) = 3\}\), and \(l = |L_D(T^n)|\). It is obvious that \(L_D(T^n)\) and \(R_D\) are disjoint subsets of subgraphs due to the assumption \(\mathcal{N}_D = \{\mathcal{E}_1\}\). Now, two possible subcases may occur:
  • 1) Suppose that \(l < \lfloor \frac{n+2}{4} \rfloor\), that is, \(-l \ge 1 \lfloor \frac{n+2}{4} \rfloor\). By fixing the graph \(G^* \cup T^n\),

\[\operatorname{cr}_{D}(G^{*}+D_{n}) \geq 4\left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor + 4(r-1) + 3l + 4(n-r-l) + 1\] \[\geq 4\left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor + 4n + \left(1 - \left\lfloor \frac{n+2}{4} \right\rfloor \right) - 3 \geq 4\left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

2) Suppose that \(l \geq \lfloor \frac{n+2}{4} \rfloor\), that is, \(2l \geq 2 \lfloor \frac{n+2}{4} \rfloor\). For any \(T^k \in L_D(T^n)\), it is not difficult to prove that \(\operatorname{cr}_D(G^*, T^k) = 2\) and \(\operatorname{cr}_D(T^n, T^k) = 1\) provided by the set \(S_D\) is empty. Moreover, it is easy to verify that the rotation \(\operatorname{rot}_D(t_k)\) is either (15324) or (14523). Since the minimum number of interchanges of adjacent elements of (15324)

On the crossing number of join product of the discrete graph ... | Michal Staš

required to produce \(\overline{(14523)}=(13254)\) is two, \(\operatorname{cr}_D(T^{k_1},T^{k_2})\geq 2+2\) holds for any two subgraphs \(T^{k_1},T^{k_2}\in L_D(T^n)\) with \(\operatorname{rot}_D(t_{k_1})\neq\operatorname{rot}_D(t_{k_2})\). Consequently, by fixing the graph \(G^*\cup T^n\cup T^k\), we have

\[\operatorname{cr}_{D}(G^{*} + D_{n}) \ge 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 5(r-1) + 7(l-1) + 5(n-r-l) + 3 + 1\] \[\ge 4 \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor + 5n + 2 \left\lfloor \frac{n+2}{4} \right\rfloor - 8 \ge 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor.\]

Thus, it was shown in all mentioned cases that there is no good drawing D of the graph \(G^* + D_n\) with fewer than \(4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor\) crossings. This completes the proof of Theorem 3.1.

4. Corollaries

Figure 4. Two graphs \(G_1\), and \(G_2\) by adding new edges to the graph \(G^*\).

Let \(G_1\) (\(G_2\)) be the graph obtained from \(G^*\) by adding the edge \(v_1v_5\) (\(v_1v_5\) and \(v_2v_5\)) in the subdrawing in Figure 1(a). Since we are able to add both edges \(v_1v_5\) and \(v_2v_5\) to the graph \(G^*\) without additional crossings in Figure 3, the drawings of the graphs \(G_1 + D_n\) and \(G_2 + D_n\) with \(4\left\lfloor \frac{n}{2}\right\rfloor \left\lfloor \frac{n-1}{2}\right\rfloor + n + \left\lfloor \frac{n}{2}\right\rfloor\) crossings are obtained. On the other hand, \(G^* + D_n\) is a subgraph of each \(G_i + D_n\), and therefore, \(\operatorname{cr}(G_i + D_n) \geq \operatorname{cr}(G^* + D_n)\) for any i = 1, 2. Thus, the next results are obvious.

Corollary 4.1. \[\operatorname{cr}(G_i + D_n) = 4 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor + n + \left\lfloor \frac{n}{2} \right\rfloor\] for \(n \geq 1\), where \(i = 1, 2\).

Acknowledgement

The author thanks the referees for very careful readings and many constructive comments to improve the quality of the paper.

References

• [1] Š. Berežný and J. Buša Jr., Algorithm of the Cyclic-Order Graph Program (Implementation and Usage), Math. Model. Geom. 7(3) (2019), 1–8.
• [2] Š. Berežný and M. Staš, Cyclic permutations and crossing numbers of join products of two symmetric graphs of order six, Carpathian J. Math. 35(2) (2019), 137–146.

• [3] S. Bere ˇ znˇ y and M. Sta ´ s, On the crossing number of join of the wheel on six vertices with the ˇ discrete graph, Carpathian J. Math. 36(3) (2020), 381–390.
• [4] M. R. Garey and D. S. Johnson, Crossing number is NP-complete. SIAM J. Algebraic. Discrete Methods 4 (1983), 312–316.
• [5] R. K. Guy, A combinatorial problem, Bull. Malayan Math. Soc. 7 (1960), 68–72.
• [6] C. Hernandez-V ´ elez, C. Medina and G. Salazar, The optimal drawing of ´ K5,n, Electronic Journal of Combinatorics 21(4), ] P4.1 (2014), 29 pp.
• [7] D. J. Kleitman, The crossing number of K5,n, J. Combinatorial Theory 9 (1970), 315–323.
• [8] M. Klesˇc, On the Crossing Numbers of Cartesian Products of Stars and Graphs on Five Ver- ˇ tices, Combinatorial Algorithms, 5874 (2009), 324–333.
• [9] M. Klesˇc, The crossing numbers of join of the special graph on six vertices with path and ˇ cycle, Discrete Math. 310(9) (2010), 1475–1481.
• [10] M. Klesˇc and E. Dra ˇ zensk ˇ a, The crossing numbers of products of the graph ´ K2,2,² with stars, Carpathian J. Math. 24(3) (2008), 327–331.
• [11] M. Klesˇc and ˇ S. Schr ˇ otter, The crossing numbers of join of paths and cycles with two graphs ¨ of order five, Combinatorial Algorithms, Springer, LNCS 7125 (2012), 160–167.
• [12] M. Klesˇc and ˇ S. Schr ˇ otter, The crossing numbers of join products of paths with graphs of ¨ order four, Discuss. Math. Graph Theory 31(2) (2011), 321–331.
• [13] A. A. G. Ngurah and R. Simanjuntak, On the super edge-magic deficiency of join product and chain graphs, Electron. J. Graph Theory Appl. 7 (1) (2019), 157–167.
• [14] M. Stas, On the crossing number of the join of the discrete graph with one graph of order ˇ five, Mathematical Modelling and Geometry 5(2) (2017), 12–19.
• [15] M. Stas, Determining crossing number of join of the discrete graph with two symmetric ˇ graphs of order five, Symmetry 11(2) (2019), 1–9.
• [16] M. Stas, On the crossing number of join of the wheel on five vertices with the discrete graph, ˇ Bull. Aust. Math. Soc. 101(3) (2020), 353–361.
• [17] D. R. Woodall, Cyclic-order graphs and Zarankiewicz's crossing number conjecture, J. Graph Theory 17 (1993), 657–671.