On the Crossing Numbers of the Join Products of Six Graphs of Order Six with Paths and Cycles

Abstract

The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. The main purpose of this paper is to determine the crossing numbers of the join products of six symmetric graphs on six vertices with paths and cycles on n vertices. The idea of configurations is generalized for the first time onto the family of subgraphs whose edges cross the edges of the considered graph at most once, and their lower bounds of necessary numbers of crossings are presented in the common symmetric table. Some proofs of the join products with cycles are done with the help of several well-known auxiliary statements, the idea of which is extended by a suitable classification of subgraphs that do not cross the edges of the examined graphs.

1. Introduction

We consider finite and simple graphs G with the vertex set $V\left(G\right)$ and the edge set $E\left(G\right)$, and refer to Klešč [1] for further notation and terminology. The crossing number $\mathrm{cr}\left(G\right)$ of a graph G is the minimum possible number of edge crossings over all drawings of G in the plane. It is well known that a drawing with a minimum number of crossings called 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 are incident with the same vertex cross. Let D be a good drawing of the graph G. We denote the number of crossings in D by ${\mathrm{cr}}_D\left(G\right)$. If $G_i$ and $G_j$ are edge-disjoint subgraphs of G, we denote the number of crossings between edges of $G_i$ and edges of $G_j$ by ${\mathrm{cr}}_D(G_i,G_j)$, and the number of crossings among edges of $G_i$ in D by ${\mathrm{cr}}_D\left(G_i\right)$.

Many applications have the problem of reducing the number of edge crossings in the drawings of graphs; one of the most popular areas is the implementation of a VLSI layout, which caused a revolution in circuit design and has a strong influence on parallel computations. So, the mentioned problem is, therefore, investigated not only by the graph theory, but also by a lot of computer scientists in an effort to, for example, minimize the number of joints on the motherboards of computers. Since edge crossings in clustered level graphs are very similar to edge crossings in level graphs, a cross minimization has its application also in the graph-state quantum computation; see Bachmaier et al. [2]. Garey and Johnson [3] proved that calculation of the crossing number of a given simple graph in general is an NP-complete problem. A survey of the exact values of the crossing numbers for several families of graphs can be found by Clancy et al. [4].

Throughout this paper, Kleitman’s result [5] on the crossing numbers for some complete bipartite graphs $K_{m,n}$ are used in several parts of proofs. He proved that

$$\mathrm{cr}\left(K_{m,n}\right)=⌊\frac{m}{2}⌋⌊\frac{m-1}{2}⌋⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋,\mathrm{if}m\le 6.$$

(1)

The join product of two graphs $G_i$ and $G_j$, denoted as $G_i+G_j$, is obtained from vertex-disjoint copies of $G_i$ and $G_j$ by adding all edges between $V\left(G_i\right)$ and $V\left(G_j\right)$. For $\left|V\right(G_i\left)\right|=m$ and $\left|V\right(G_j\left)\right|=n$, the edge set of $G_i+G_j$ is the union of the disjoint edge sets of the graphs $G_i$, $G_j$ and $K_{m,n}$. Let $D_n$, $P_n$, and $C_n$ be the discrete graph, the path, and the cycle on n vertices, respectively. The crossings numbers of the join products of all graphs of order at most four with paths and cycles have been well known for a long time by Klešč [6,7], and Klešč and Schrötter [8]. We present a new technique of recalculating the number of crossings due to the combined fixation of different types of subgraphs in an effort to achieve the crossings numbers of $G+P_n$ and $G+C_n$ also for all graphs G of orders five and six. Of course, $\mathrm{cr}(G+P_n)$ and $\mathrm{cr}(G+C_n)$ are already known for a lot of connected graphs G of orders five and six [1,9,10,11,12,13,14,15,16,17], but only for some disconnected graphs [18,19,20].

Let $G^{*}$ be the graph of order six consisting of one 4-cycle and a path $P_3$, whose one end vertex is identical to one vertex of the 4-cycle. The crossing number of $G^{*}+D_n$ equal to $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ is determined in Theorem 1 with the proof that is strongly based on different symmetries between the investigated subgraph configurations in $G^{*}+D_n$. Here, the idea of configurations is generalized onto the family of subgraphs whose edges cross the edges of $G^{*}$ at most once, and the obtained lower bounds of necessary numbers of crossings are presented in the common symmetric

Table 1. The minimum numbers of edge crossings between two different subgraphs $T^i$ and $T^j$ for two configurations ${\mathcal{X}}_p$ and ${\mathcal{Y}}_q$ of the subgraphs $F^i$ and $F^j$, respectively.

-	${\mathcal{A}}_1$	${\mathcal{A}}_2$	${\mathcal{A}}_3$	${\mathcal{A}}_4$	${\mathcal{B}}_1$	${\mathcal{B}}_2$
${\mathcal{A}}_1$	6	3	5	4	1	4
${\mathcal{A}}_2$	3	6	4	5	4	1
${\mathcal{A}}_3$	5	4	6	5	2	3
${\mathcal{A}}_4$	4	5	5	6	3	2
${\mathcal{B}}_1$	1	4	2	3	6	1
${\mathcal{B}}_2$	4	1	3	2	1	6

. Note that we are unable to establish $\mathrm{cr}(G^{*}+D_n)$ using the methods presented in [21] because there is a possibility to obtain a subgraph $T^j$ with ${\mathrm{cr}}_D(T^i,T^j)=1$ and ${\mathrm{cr}}_D(G^{*},T^j)=1$ in some subdrawing $D(G^{*}\cup T^i)$ induced by a drawing D of $G^{*}+D_n$ in which ${\mathrm{cr}}_D(G^{*},T^i)=0$; see also Table 1. The result of the main Theorem 1 can be extended to the same crossing number of $G^{*}+P_n$ in Corollary 2, using two special drawings of $G^{*}+P_n$ for n even and odd. The crossing numbers of $G_i+D_n$ for two other graphs $G_i$ of order six are given in Corollaries 1 and 3 by adding new edges to the graph $G^{*}$.

Let $H^{*}$ be the graph on six vertices consisting of one 4-cycle and two leaves adjacent to two different but not opposite vertices of the 4-cycle. In [22], Staš proved the crossing number of $H^{*}+D_n$ for $n\ge 1$ using the properties of cyclic permutations. The crossing number of $H^{*}+P_n$ is given using its good drawing and presented in Corollary 5. Consequently, the obtained values of $\mathrm{cr}(G^{*}+P_n)$ and $\mathrm{cr}(H^{*}+P_n)$ help us to state $\mathrm{cr}(G_1+P_n)$ as the result of Theorem 5, thanks to multiple symmetries of the graph $G_1$. $\mathrm{cr}(H_i+P_n)$ also for two other graphs $H_i$ of order six are presented in Theorems 3 and 4 by adding new edges to the graph $H^{*}$.

The paper concludes by giving the crossing numbers of the join products of the six graphs of order six mentioned above with the cycles $C_n$. Additionally, in this paper, some proofs are supported by two well-known auxiliary statements: Lemmas 5 and 6.

2. Cyclic Permutations and Configurations

Let $G^{*}$ be the connected graph on six vertices such that it contains as a subgraph one 4-cycle and a path $P_3$ whose one end vertex is identical to one vertex of the 4-cycle (for brevity, we write $C_4^{\star }$). Without lost of generality, let $V\left(G^{*}\right)=\{v_1,v_2,\cdots ,v_6\}$, and let $v_3{v}_4{v}_5{v}_6{v}_3$ and $v_1{v}_2{v}_3$ be the vertex notation of the 4-cycle $C_4^{\star }$ and the path on three vertices in all our considered good drawings of $G^{*}$, respectively. Notice that each join product $G^{*}+D_n$ consists of exactly one copy of the mentioned graph $G^{*}$ and n different vertices $t_1,\cdots ,t_n$, where each such vertex $t_i$ is adjacent to any vertex of $G^{*}$. Throughout the paper, we denote by $T^i$ the subgraph of $G^{*}+D_n$ induced by the six edges incident with the vertex $t_i$. This enforces that the considered graph $T^1\cup \cdots \cup T^n$ is isomorphic to $K_{6,n}$, which yields

$$G^{*}+D_n=G^{*}\cup K_{6,n}=G^{*}\cup \left(\bigcup _{i=1}^n{T}^i\right).$$

(2)

In any drawing D of the join product $G^{*}+D_n$, by the rotation ${\mathrm{rot}}_D\left(t_i\right)$ of a vertex $t_i$, we understand the cyclic permutation that records the (cyclic) counter-clockwise order in which the edges leave $t_i$. See also Hernández-Vélez et al. [23] and Woodall [24]. We use the notation $\left(123456\right)$ if the counter-clockwise order of 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$. Notice that a rotation is a cyclic permutation, and therefore, we try to represent each cyclic permutation by the permutation with 1 in the first position whenever possible. Let ${\overline{\mathrm{rot}}}_D\left(t_i\right)$ denote the inverse permutation of ${\mathrm{rot}}_D\left(t_i\right)$. In the paper, it is very helpful to separate n different subgraphs $T^i$ of $G^{*}+D_n$ into three subsets depending on the number of crossings between $T^i$ and $G^{*}$ in D. Let $R_D=\{T^i:{\mathrm{cr}}_D(G^{*},T^i)=0\}$ and $S_D=\{T^i:{\mathrm{cr}}_D(G^{*},T^i)=1\}$. Each remaining subgraph $T^i$ crosses the edges of $G^{*}$ more than once. For any $T^i\in R_D\cup S_D$, we also write $F^i$ instead of $G^{*}\cup T^i$.

We also have to emphasize that there at least $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings in each good drawing D of $G^{*}+D_n$ with the empty set $R_D$ provided by

$${\mathrm{cr}}_D(G^{*}+D_n)={\mathrm{cr}}_D\left(K_{6,n}\right)+{\mathrm{cr}}_D\left(G^{*}\right)+{\mathrm{cr}}_D(G^{*},K_{6,n})\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+n$$

$$\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋.$$

According to the expected result of Theorem 1, this leads to a consideration of the nonempty set $R_D$ in all good drawings of $G^{*}+D_n$. As we can always redraw a crossing of two edges of $C_4^{\star }$ to get a new drawing of $C_4^{\star }$ (with vertices in a different order) with fewer edge crossings, the proof of Lemma 1 can be omitted. It is also well known that the same crossing number is obtained for two isomorphic subdrawings of one graph induced by any drawing of the join product with another graph.

Lemma 1.

In any optimal drawing D of the join product $G^{*}+D_n$, the edges of $C_4^{\star }$ do not cross each other. Moreover, the subdrawing of $G^{*}$ induced by D, in which there is a possibility to obtain a subgraph $T^i\in R_D$, is isomorphic to one of the two drawings depicted in Figure 1.

Assume a good drawing D of the join product $G^{*}+D_n$ in which the edges of $G^{*}$ do not cross each other. For this purpose, consider the planar drawing of the graph $G^{*}$ as shown in Figure 1a. For subgraphs $T^i\in R_D$, we establish all possible rotations ${\mathrm{rot}}_D\left(t_i\right)$ which could appear in the considered drawing D. Clearly, there is only one subdrawing of $F^i\backslash \{v_2,v_3\}$ and can be represented by the subrotation $\left(1654\right)$. We have just four possibilities of getting a subdrawing of $F^i=G^{*}\cup T^i$, depending on which of the two regions the edges $t_i{v}_2$ and $t_i{v}_3$ can be placed in. Thus, there are four different cyclic permutations for ${\mathrm{rot}}_D\left(t_i\right)$ with ${\mathrm{cr}}_D(G^{*},T^i)=0$, namely, the cyclic permutations $\left(123654\right)$, $\left(165432\right)$, $\left(136542\right)$, and $\left(126543\right)$. Let us denote these cyclic permutations by ${\mathcal{A}}_1=\left(123654\right)$, ${\mathcal{A}}_2=\left(165432\right)$, ${\mathcal{A}}_3=\left(136542\right)$, and ${\mathcal{A}}_4=\left(126543\right)$. We say that a subdrawing of $F^i$ has the configuration ${\mathcal{A}}_p$, if ${\mathrm{rot}}_D\left(t_i\right)={\mathcal{A}}_p$ for some $p\in \{1,2,3,4\}$. Suppose their drawings are as shown in Figure 2 because it does not matter which of the regions in $D(G^{*}\cup T^i)$ is unbounded in our considerations.

In a contemplated good drawing of the graph $G^{*}+D_n$ with the planar subdrawing of $G^{*}$, some configuration ${\mathcal{A}}_p$ may not appear. Hence, let ${\mathcal{M}}_D$ denote the set of all existing configurations ${\mathcal{A}}_p$ in the considered drawing D such that they are included in the set $\mathcal{M}=\{{\mathcal{A}}_1,{\mathcal{A}}_2,{\mathcal{A}}_3,{\mathcal{A}}_4\}$. Figure 2 also points to the possibilities of obtaining a subgraph $T^k\in S_D$ with ${\mathrm{cr}}_D(T^i,T^k)=1$ and ${\mathrm{cr}}_D(T^i,T^k)=2$ for any subgraph $F^i$ with the configuration ${\mathcal{A}}_1$, ${\mathcal{A}}_2\in {\mathcal{M}}_D$ and ${\mathcal{A}}_3$, ${\mathcal{A}}_4\in {\mathcal{M}}_D$, respectively. For this purpose, there are two different cyclic permutations for ${\mathrm{rot}}_D\left(t_k\right)$ with ${\mathrm{cr}}_D(G^{*},T^k)=1$, namely, the cyclic permutations $\left(154632\right)$ and $\left(123465\right)$. Let us denote these two cyclic permutations by ${\mathcal{B}}_1=\left(154632\right)$ and ${\mathcal{B}}_2=\left(123465\right)$. We say that a subdrawing of $F^k$ has the configuration ${\mathcal{B}}_q$, if $T^k\in S_D$ and ${\mathrm{rot}}_D\left(t_k\right)={\mathcal{B}}_q$ for $q\in \{1,2\}$. In view of our other considerations, suppose their drawings are as shown in Figure 3. Obviously, ${\mathrm{rot}}_D\left(t_l\right)$ equal to either $\left(154632\right)$ or $\left(123465\right)$ may not force just one crossing on only some edge of $G^{*}$ by the corresponding subgraph $T^l$ if the vertex $t_l$ is placed in the outer region of $D\left(G^{*}\right)$ with the four vertices $v_3$, $v_4$, $v_5$, and $v_6$ of $G^{*}$ on its boundary. As in the previous case of four possible configurations, let ${\mathcal{N}}_D$ denote the set of all existing configurations ${\mathcal{B}}_q$ in the considered drawing D such that they are included in the set $\mathcal{N}=\{{\mathcal{B}}_1,{\mathcal{B}}_2\}$.

Now, our aim is to establish a minimum number of edge crossings between two different subgraphs $F^i$ and $F^j$ using the idea of mentioned configurations. For two configurations $\mathcal{X}$ and $\mathcal{Y}$ from ${\mathcal{M}}_D$ (not necessarily different), let ${\mathrm{cr}}_D(\mathcal{X},\mathcal{Y})$ denote the number of edge crossings in $D(T^i\cup T^j)$ for two different subgraphs $T^i,T^j\in R_D$ such that $F^i$, $F^j$ have configurations $\mathcal{X}$, $\mathcal{Y}$, respectively. We denote by $\mathrm{cr}(\mathcal{X},\mathcal{Y})$ the minimum value of ${\mathrm{cr}}_D(\mathcal{X},\mathcal{Y})$ over all pairs $\mathcal{X}$ and $\mathcal{Y}$ from $\mathcal{M}$ among all good drawings D of the join product $G^{*}+D_n$. In the following, our goal is to determine the lower bounds of $\mathrm{cr}(\mathcal{X},\mathcal{Y})$ for all possible pairs $\mathcal{X},\mathcal{Y}\in \mathcal{M}$ and we also partially extend this idea of lower bounds to a subfamily of subgraphs by which the edges $G^{*}$ are crossed exactly once, that is, for subgraphs with the configurations ${\mathcal{B}}_1$ and ${\mathcal{B}}_2$.

At least five interchanges of adjacent elements of $\left(123654\right)$ are necessary to obtain cyclic permutation $\overline{\left(136542\right)}=\left(124563\right)$ because only one interchange of the adjacent elements of $\left(123654\right)$ produces the cyclic permutation $\left(136542\right)$. (Let $T^x$ and $T^y$ be any two different subgraphs represented by their $\mathrm{rot}\left(t_x\right)$ and $\mathrm{rot}\left(t_y\right)$ of the same length m, where m is a positive integer of at least 3. If the minimum number of interchanges of adjacent elements of $\mathrm{rot}\left(t_x\right)$ required to produce $\mathrm{rot}\left(t_y\right)$ is at most z, then ${\mathrm{cr}}_D(T^x,T^y)\ge ⌊\frac{m}{2}⌋⌊\frac{m-1}{2}⌋-z$, see also Woodall [24].) Using this knowledge, the edges of each subgraph $T^i$ with the configuration ${\mathcal{A}}_1$ of $F^i$ are crossed at least five times by the edges of each subgraph $T^j$ with the configuration ${\mathcal{A}}_3$ of $F^j$, that is, $\mathrm{cr}({\mathcal{A}}_1,{\mathcal{A}}_3)\ge 5$. The same idea also force $\mathrm{cr}({\mathcal{A}}_1,{\mathcal{A}}_2)\ge 3$, $\mathrm{cr}({\mathcal{A}}_1,{\mathcal{A}}_4)\ge 4$, $\mathrm{cr}({\mathcal{A}}_2,{\mathcal{A}}_3)\ge 4$, $\mathrm{cr}({\mathcal{A}}_2,{\mathcal{A}}_4)\ge 5$, and $\mathrm{cr}({\mathcal{A}}_3,{\mathcal{A}}_4)\ge 3$. Moreover, by a simple discussion, we can verify that the lower bound of $\mathrm{cr}({\mathcal{A}}_3,{\mathcal{A}}_4)$ can be increased up to 5. Let $F^i$ be any subgraph with the configuration ${\mathcal{A}}_3$, and let $T^j$ be some different subgraph from $R_D$ satisfying the restriction ${\mathrm{cr}}_D(T^i,T^j)<5$. If we place the vertex $t_j$ in the region of $D(G^{*}\cup T^i)$ with the three vertices $v_2$, $v_3$ and $v_4$ of $G^{*}$ on its boundary, then the edges $t_j{v}_1$, $t_j{v}_5$ and $t_j{v}_6$ produce exactly one, one and two crossings on the edges of $T^i$, respectively. Thus, ${\mathrm{rot}}_D\left(t_j\right)=\left(165432\right)={\mathcal{A}}_2$. Other placements of the vertex $t_j$ imply at least five crossings on the edges of $T^i\cup T^j$. Clearly, also $\mathrm{cr}({\mathcal{A}}_p,{\mathcal{A}}_p)\ge 6$ for any $p=1,2,3,4$. The same method as above can be applied to establish the remaining lower bounds of two configurations from $\mathcal{M}\cup \mathcal{N}$. All resulting lower bounds are summarized in the common symmetric Table 1 in which ${\mathcal{X}}_p$ and ${\mathcal{Y}}_q$ are configurations of two different subgraphs $F^i$ and $F^j$, where $\mathcal{X},\mathcal{Y}\in \{\mathcal{A},\mathcal{B}\}$ and if $\mathcal{X}=\mathcal{A}$ or $\mathcal{Y}=\mathcal{A}$ then $p\in \{1,2,3,4\}$ or $q\in \{1,2,3,4\}$; otherwise, $p\in \{1,2\}$ or $q\in \{1,2\}$, respectively.

3. The Crossing Number of ${\mathbf{G}}^{*}+{\mathbf{D}}_{\mathbf{n}}$

In a good drawing of $G^{*}+D_n$, two different vertices $t_i$ and $t_j$ of the graph $G^{*}+D_n$ are said to be antipodal if the edges of the corresponding subgraph $T^i\cup T^j$ do not cross each other. A drawing is said to be antipode-free if it does not contain any two antipodal vertices.

Lemma 2.

For $n>2$, let D be a good and antipode-free drawing of $G^{*}+D_n$ with the subdrawing of $G^{*}$ induced by D given in Figure 1a. For some $p\in \{1,2\}$, if there is a subgraph $T^i\in R_D$ with the configuration ${\mathcal{A}}_p\in {\mathcal{M}}_D$ of $F^i$ and a subgraph $T^k\in S_D$ such that ${\mathrm{cr}}_D(T^i,T^k)=2$, then

(a) 

${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 8$ for any subgraph $T^l\in R_D$, $l\ne i$; and

(b) 

${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 7$ for any subgraph $T^l\in S_D$, $l\ne k$; and

(c) 

${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 6$ for any subgraph $T^l\notin R_D\cup S_D$.

Proof. 

Let ${\mathcal{A}}_1$ be the configuration of $F^i$ and remark that it is uniquely represented by its ${\mathrm{rot}}_D\left(t_i\right)=\left(123654\right)$. The induced subdrawing $D(G^{*}\cup T^i)$ of $F^i$ contains just six regions with the vertex $t_i$ on their boundaries. If we consider a subgraph $T^k\in S_D$ satisfying the restriction ${\mathrm{cr}}_D(T^i,T^k)=2$, then the corresponding vertex $t_k$ can only be placed in the region with the four vertices $v_1$, $v_2$, $v_3$, and $v_4$ of $G^{*}$ on its boundary. Using this knowledge, the edges $t_k{v}_1$, $t_k{v}_3$, and $t_k{v}_4$ produce no crossings on edges of $F^i$, and the edge $t_k{v}_2$ either crosses the edge $t_i{v}_1$ or does not cross any edge of $F^i$. If $t_k{v}_2$ crosses $t_i{v}_1$, then ${\mathrm{rot}}_D\left(t_k\right)=\left(125463\right)$. If the edges of $F^i$ are not crossed by $t_k{v}_2$ and also $t_k{v}_5$ crosses $v_3{v}_4$ of $G^{*}$, then ${\mathrm{rot}}_D\left(t_k\right)=\left(164532\right)$. Finally, if $t_k{v}_5$ crosses $t_i{v}_4$, then $t_k{v}_6$ crosses either $v_2{v}_3$, $t_i{v}_3$ with ${\mathrm{rot}}_D\left(t_k\right)=\left(154362\right)$ or $v_4{v}_5$, $t_i{v}_4$ with ${\mathrm{rot}}_D\left(t_k\right)=\left(156432\right)$.

In the following, we suppose $T^k\in S_D$ with ${\mathrm{rot}}_D\left(t_k\right)=\left(125463\right)$, but a similar idea can be applied to the other three cases mentioned above.

(a)

Let us assume $T^l\in R_D$, $l\ne i$, with the configuration ${\mathcal{A}}_p\in {\mathcal{M}}_D$ of $F^l$ for some $p\in \{1,\cdots ,4\}$.

Table 2. All possibilities of the configurations ${\mathcal{A}}_p$ of $F^l$ for $T^l\in R_D$ with $l\ne i$.

$\mathbf{conf}\left({\mathit{F}}^{\mathit{l}}\right)$	${\mathbf{cr}}_{\mathit{D}}({\mathit{T}}^{\mathit{i}},{\mathit{T}}^{\mathit{l}})$	${\mathbf{cr}}_{\mathit{D}}({\mathit{T}}^{\mathit{k}},{\mathit{T}}^{\mathit{l}})$	${\mathbf{cr}}_{\mathit{D}}({\mathit{T}}^{\mathit{i}}\cup {\mathit{T}}^{\mathit{k}},{\mathit{T}}^{\mathit{l}})$
${\mathcal{A}}_1$	6	2	8
${\mathcal{A}}_2$	3	5	8
${\mathcal{A}}_3$	5	3	8
${\mathcal{A}}_4$	4	4	8

summarizes the minimal values of necessary crossings among the edges in the subdrawing $D(T^i\cup T^k\cup T^l)$. The values in the first column of Table 2 are given by the lower bounds from the first column of Table 1. Moreover, the mentioned results in the second column of Table 2 are obvious for $p=1$ and $p=3$, because ${\mathrm{cr}}_D(T^j,T^l)=1$ for ${\mathcal{A}}_1$ of $F^l$ and ${\mathrm{cr}}_D(T^j,T^l)=2$ for ${\mathcal{A}}_3$ of $F^l$ can be achieved for some $T^j\in S_D$ only with the configuration ${\mathcal{B}}_1$ of $F^j$ again by Table 1 (note that ${\mathrm{rot}}_D\left(t_k\right)\ne {\mathrm{rot}}_D\left(t_j\right)$). For the configuration ${\mathcal{A}}_2$ of $F^l$, it is easy to verify in all possible regions of $D(G^{*}\cup T^l)$ that the edges of $T^l$ must be crossed by $T^k$ more than four times. Finally for $p=4$, ${\mathrm{cr}}_D(T^k,T^l)\ge ⌊\frac{6}{2}⌋⌊\frac{6-1}{2}⌋-2=4$ provided by two interchanges of adjacent elements of ${\mathrm{rot}}_D\left(t_l\right)$ produce ${\mathrm{rot}}_D\left(t_k\right)$. As $T^l\in R_D$, the minimum value in the last column of Table 2 forces the mentioned minimum number of edge crossings.

(b)

As ${\mathrm{cr}}_D(T^i,T^k)=2$ with ${\mathrm{rot}}_D\left(t_k\right)=\left(125463\right)$, the subdrawing $D(G^{*}\cup T^i\cup T^k)$ is clearly interpreted, and so it is not difficult to check in all considered regions of the induced subdrawing $D(G^{*}\cup T^i\cup T^k)$ that the edges of $G^{*}\cup T^i\cup T^k$ are crossed more than six times by any subgraph $T^l\in S_D$, $l\ne k$. The second way is to use the software COGA created by Berežný and Buša [25] to generate all permutations of six elements in which we need at most five exchanges of adjacent elements to achieve both rotations, ${\mathrm{rot}}_D\left(t_i\right)$ and ${\mathrm{rot}}_D\left(t_k\right)$.

(c)

Let $T^l$ be any subgraph whose edges cross the edges of $G^{*}$ more than once. As ${\mathrm{cr}}_D(T^i,T^k)=2$ and ${\mathrm{cr}}_D\left(K_{6,3}\right)\ge 6$ by (1), the edges of $T^i\cup T^k$ must be crossed at least four times by $T^l$, which yields ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 2+4=6$.

Due to the symmetry of the configurations ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$, the proof can proceed in the same way also for the configuration ${\mathcal{A}}_2$ of $F^i$, and so the proof of Lemma 2 is done. □

Lemma 3

(See [26] Lemma 3.1). For $n>2$, let D be a good and antipode-free drawing of $G^{*}+D_n$. Let $2|R_D|+|S_D|>2⌈\frac{n}{2}⌉$, and let $T^i,T^j\in R_D$ be two different subgraphs with ${\mathrm{cr}}_D(T^i\cup T^j)\ge 4$. If both conditions

$${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^j,T^l)\ge 10forany{T}^l\in R_D\backslash \{T^i,T^j\},$$

(3)

$${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^j,T^k)\ge 7forany{T}^k\in S_D$$

(4)

hold, then there are at least $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings in D.

Lemma 4.

$\mathrm{cr}(G^{*}+D_1)=0$ and $\mathrm{cr}(G^{*}+D_2)=2$.

Proof. 

The graph $G^{*}+D_1$ is planar, and so $\mathrm{cr}(G^{*}+D_1)=0$. Let H be the graph of order five consisting of one 4-cycle $v_3{v}_4{v}_5{v}_6{v}_3$ and one leaf $v_2$ adjacent to the vertex $v_3$. This was proved by Klešč and Schrötter [12] that $\mathrm{cr}(H+P_2)=2$. As $G^{*}+D_2$ contains a subgraph that is a subdivision of $H+P_2$, we obtain $\mathrm{cr}(G^{*}+D_2)\ge \mathrm{cr}(H+P_2)=2$. The proof of Lemma 4 is done due to the subdrawing of the graph $G^{*}+D_2$ having exactly two crossings in Figure 4. □

Theorem 1.

$\mathrm{cr}(G^{*}+D_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ for $n\ge 1$.

Proof. 

The good drawing of the join product $G^{*}+D_n$ with exactly $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings in Figure 4 enforces the required upper border, that is, $\mathrm{cr}(G^{*}+D_n)\le 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$. To prove the lower border by induction on n, suppose that for some $n\ge 3$ using Lemma 4, there is a drawing D such that

$${\mathrm{cr}}_D(G^{*}+D_n)<6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋,$$

(5)

and let also

$$\mathrm{cr}(G^{*}+D_m)=6⌊\frac{m}{2}⌋⌊\frac{m-1}{2}⌋+2⌊\frac{m}{2}⌋\mathrm{for}\mathrm{any}2\le m<n.$$

(6)

We first show that the considered drawing D is with no antipodal vertices. For this purpose, let ${\mathrm{cr}}_D(T^i,T^j)=0$ hold for two different subgraphs $T^i$ and $T^j$. If at least one of $T^i$ and $T^j$, say $T^i$, does not cross the edges of $G^{*}$, then the edges of $G^{*}\cup T^i$ must be crossed by $T^j$ more than once, that is, ${\mathrm{cr}}_D(G^{*}\cup T^i,T^j)\ge 2$. If $T^i,T^j\notin R_D$, then ${\mathrm{cr}}_D(G^{*},T^i\cup T^j)\ge 2$. The well-known fact $\mathrm{cr}\left(K_{6,3}\right)=6$ by (1) produces at least six crossings on the edges of $T^i\cup T^j$ by each other subgraph $T^k$, $k\ne i,j$. So, the number of crossings in D satisfies

$${\mathrm{cr}}_D(G^{*}+D_n)={\mathrm{cr}}_D\left(G^{*}+D_{n-2}\right)+{\mathrm{cr}}_D(T^i\cup T^j)+{\mathrm{cr}}_D(K_{6,n-2},T^i\cup T^j)+{\mathrm{cr}}_D(G^{*},T^i\cup T^j)$$

$$\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+2⌊\frac{n-2}{2}⌋+0+6(n-2)+2=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋.$$

The obtained contradiction with the assumption (5) does not allow the existence of two antipodal vertices, that is, D is an antipode-free drawing. If we use the notation $r=|R_D|$ and $s=|S_D|$, then ${\mathrm{cr}}_D\left(K_{6,n}\right)\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋$ again by (1) together with (5) force the following relation with respect to the edge crossings of the subgraph $G^{*}$ in D:

$${\mathrm{cr}}_D\left(G^{*}\right)+\sum _{T^i\in R_D}{\mathrm{cr}}_D(G^{*},T^i)+\sum _{T^i\in S_D}{\mathrm{cr}}_D(G^{*},T^i)+\sum _{T^i\notin R_D\cup S_D}{\mathrm{cr}}_D(G^{*},T^i)<2⌊\frac{n}{2}⌋,$$

i.e.,

$${\mathrm{cr}}_D\left(G^{*}\right)+0r+1s+2(n-r-s)<2⌊\frac{n}{2}⌋.$$

(7)

The mentioned inequality (7) subsequently enforces $2r+s>2n-2⌊\frac{n}{2}⌋=2\lceil \frac{n}{2}\rceil$, that is, $r\ge 1$ and $r>n-r-s$. As the set $R_D$ is nonempty, we deal with the possibilities of obtaining a subgraph $T^i\in R_D$, and a contradiction with the assumption (5) is reached in all considered cases.

Case 1:${\mathrm{cr}}_D\left(G^{*}\right)=0$. As $r\ge 1$, we consider the subdrawing of $G^{*}$ induced by D given in Figure 1a and we deal with the possible configurations ${\mathcal{A}}_p$ from the nonempty set ${\mathcal{M}}_D$. For $p\in \{1,2\}$, let us first consider that ${\mathcal{A}}_p\in {\mathcal{M}}_D$ and let also for some $T^i\in R_D$ with the configuration ${\mathcal{A}}_p$ of $F^i$ there is a subgraph $T^k\in S_D$ by which the edges of $T^i$ are crossed exactly twice. Then, by fixing the subgraph $G^{*}\cup T^i\cup T^k$ and using the lower bounds in Lemma 2, we have

$$\begin{array}{c}{\mathrm{cr}}_D(G^{*}+D_n)={\mathrm{cr}}_D\left(K_{6,n-2}\right)+{\mathrm{cr}}_D(K_{6,n-2},G^{*}\cup T^i\cup T^k)+{\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k)\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋\\ +8(r-1)+7(s-1)+6(n-r-s)+3\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+7(n-2)+3\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋.\end{array}$$

This contradicts the assumption (5). Therefore, suppose that for any $T^k\in S_D$, ${\mathrm{cr}}_D(T^i,T^k)\ne 2$ holds for each subgraph $T^i\in R_D$ with the configuration ${\mathcal{A}}_p$ of $F^i$, $p\in \{1,2\}$. In the following, we discuss two main subcases with respect to whether the set ${\mathcal{N}}_D$ is empty or not.

Subcase 1: Let ${\mathcal{N}}_D$ be an empty set, that is, the edges of $G^{*}\cup T^i$ are crossed more than three times by any subgraph $T^k\in S_D$, where $T^i\in R_D$ with some configuration ${\mathcal{A}}_p\in {\mathcal{M}}_D$ of $F^i$.

i.

$\{{\mathcal{A}}_1,{\mathcal{A}}_2\}\subseteq {\mathcal{M}}_D$. In the rest of the paper, assume two different subgraphs $T^{n-1},T^n\in R_D$ such that $F^{n-1}$ and $F^n$ have mentioned configurations ${\mathcal{A}}_1$ and ${\mathcal{A}}_2$, respectively. By summing the values in the first two rows for four possible columns of Table 1 we obtain ${\mathrm{cr}}_D(G^{*}\cup T^{n-1}\cup T^n,T^i)\ge 9$ for any $T^i\in R_D$ with $i\ne n-1,n$. Using a relatively strong assumption of Subcase 1, any subgraph $T^k\in S_D$ crosses the edges of both $G^{*}\cup T^{n-1}$ and $G^{*}\cup T^n$ more than three times. This in turn means that ${\mathrm{cr}}_D(G^{*}\cup T^{n-1}\cup T^n,T^k)\ge 1+3+3=7$ trivially holds for any $T^k\in S_D$. Each of $n-r-s$ subgraph $T^l\notin R_D\cup S_D$ of $K_{6,n-2}$ crosses $G^{*}\cup T^{n-1}\cup T^n$ more than four times using ${\mathrm{cr}}_D(T^{n-1}\cup T^n,T^l)\ge 3$. As ${\mathrm{cr}}_D(G^{*}\cup T^{n-1}\cup T^n)\ge 3$, by fixing the subgraph $G^{*}\cup T^{n-1}\cup T^n$, we have

$$\begin{array}{c}{\mathrm{cr}}_D(G^{*}+D_n)\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+9(r-2)+7s+5(n-r-s)+3\\ =6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+5n+2(2r+s)-15\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+5n+2\left(2⌈\frac{n}{2}⌉+1\right)-15,\end{array}$$

where the obtained number of crossings $6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+5n+4⌈\frac{n}{2}⌉-13$ contradicts the assumption (5) only for n odd. For n even, it also applies if ${\mathrm{cr}}_D(T^{n-1}\cup T^n)>3$ or $2r+s>n+1$. Suppose the case for ${\mathrm{cr}}_D(T^{n-1}\cup T^n)=3$ and $2r+s=n+1$, which yields $s\ge 1$. This knowledge enables us to add at least one more crossing into the mentioned number of crossings $6\frac{n-2}{2}\frac{n-4}{2}+5n+4\frac{n}{2}-13$, because over 14 possible regions of the symmetric subdrawing $D(G^{*}\cup T^{n-1}\cup T^n)$, the edges of $G^{*}\cup T^{n-1}\cup T^n$ are crossed at least eight times by each $T^k\in S_D$. This also confirms a contradiction with the assumption in D.

ii.

$\{{\mathcal{A}}_1,{\mathcal{A}}_2\}⊈{\mathcal{M}}_D$. If ${\mathcal{A}}_p\in {\mathcal{M}}_D$ for only $p\in \{3,4\}$, by fixing the subgraph $G^{*}\cup T^i$ for some $T^i\in R_D$, we have

$${\mathrm{cr}}_D(G^{*}+D_n)\ge 6⌊\frac{n-1}{2}⌋⌊\frac{n-2}{2}⌋+5(r-1)+4s+3(n-r-s)+0$$

$$\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+4(n-1)\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋.$$

Of course, the same idea for the cases of $\{{\mathcal{A}}_1,{\mathcal{A}}_3\}\subseteq {\mathcal{M}}_D$ and $\{{\mathcal{A}}_2,{\mathcal{A}}_4\}\subseteq {\mathcal{M}}_D$ forces the same result because ${\mathrm{cr}}_D(T^i,T^j)\ge 5$ is also provided using the values in Table 1 for any subgraph $T^j\in R_D$, $j\ne i$ if we fix the subgraph $G^{*}\cup T^i$ with the configuration ${\mathcal{A}}_3$ and ${\mathcal{A}}_4$ of $F^i$, respectively. All these subcases contradict the assumption (5) in D, and therefore, the case of $|{\mathcal{M}}_D|=2$ offers only two possibilities of either ${\mathcal{M}}_D=\{{\mathcal{A}}_1,{\mathcal{A}}_4\}$ or ${\mathcal{M}}_D=\{{\mathcal{A}}_2,{\mathcal{A}}_3\}$. If we fix any two subgraphs $T^i,T^j\in R_D$ such that $F^i,F^j$ have the configurations ${\mathcal{A}}_1$ and ${\mathcal{A}}_4$, respectively, then Table 1 confirms that the condition (3) holds. The condition (4) follows from the special assumption ${\mathcal{N}}_D=\varnothing$ of Subcase 1. As ${\mathrm{cr}}_D(T^i\cup T^j)\ge 4$, the discussed drawing again contradicts the assumption of D by Lemma 3. Finally, if ${\mathcal{M}}_D=\left\{{\mathcal{A}}_p\right\}$ for only one $p\in \{1,2\}$, the proof can proceed in the same way as in the case of ${\mathcal{A}}_p\in {\mathcal{M}}_D$ for only $p\in \{3,4\}$.

Subcase 2: Let ${\mathcal{N}}_D$ be a nonempty set, that is, there is a possibility to obtain a subgraph $T^k\in S_D$ satisfying ${\mathrm{cr}}_D(G^{*}\cup T^i,T^k)\ge 2$ for some $T^i\in R_D$ with either ${\mathcal{A}}_1$ or ${\mathcal{A}}_2$ of $F^i$. Let us denote $S_D\left({\mathcal{B}}_1\right)=\{T^k\in S_D:{\mathrm{rot}}_D\left(t_k\right)=\left(154632\right)\}$, $S_D\left({\mathcal{B}}_2\right)=\{T^k\in S_D:{\mathrm{rot}}_D\left(t_k\right)=\left(123465\right)\}$, and consequently $s_1=\left|S_D\left({\mathcal{B}}_1\right)\right|$, $s_2=\left|S_D\left({\mathcal{B}}_2\right)\right|$. Notice that $S_D\left({\mathcal{B}}_1\right)$ and $S_D\left({\mathcal{B}}_2\right)$ are two disjoint subsets of $S_D$, and $s_1+s_2\le s$, that is, $s-s_1-s_2\ge 0$. Using their symmetry, let $s_1$ be greater than $s_2$ provided that at least one of the sets $S_D\left({\mathcal{B}}_1\right)$ and $S_D\left({\mathcal{B}}_2\right)$ is nonempty. Now, we discuss the four possible subcases:

i.

${\mathcal{A}}_1\in {\mathcal{M}}_D$ and assume some subgraph $F^i$, having the configuration ${\mathcal{A}}_1$. Let $T^k$ be a subgraph from the nonempty set $S_D\left({\mathcal{B}}_1\right)$. By summing the values in two considered rows for four possible columns of Table 1, we obtain ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^j)\ge 7$ for any $T^j\in R_D$ with $j\ne i$. The subgraph $F^k$ is represented by the cyclic permutation $\left(154632\right)$, and so ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 1+1+6=8$ holds for any other $T^l\in S_D\left({\mathcal{B}}_1\right)$, $l\ne k$. Moreover, ${\mathrm{cr}}_D(T^i\cup T^k,T^l)\ge 5$ is fulfilling for any $T^l$ with $l\ne i,k$ because five interchanges of adjacent elements of ${\mathrm{rot}}_D\left(t_i\right)$ produce ${\mathrm{rot}}_D\left(t_k\right)$. This forces ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 1+5=6$ for any $T^l\in S_D\left({\mathcal{B}}_2\right)$ and ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 2+5=7$ for any $T^l\notin R_D\cup S_D$. As ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k)\ge 2$, by fixing the subgraph $G^{*}\cup T^i\cup T^k$, we have

$${\mathrm{cr}}_D(G^{*}+D_n)\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+7(r-1)+8(s_1-1)+6s_2+7(s-s_1-s_2)+7(n-r-s)+2$$

$$=6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+7n+(s_1-s_2)-13\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋.$$

.

ii.

${\mathcal{A}}_1\notin {\mathcal{M}}_D$ and ${\mathcal{A}}_3\in {\mathcal{M}}_D$. Let us assume the configuration ${\mathcal{A}}_3$ of some subgraph $F^i$, and let $T^k\in S_D\left({\mathcal{B}}_1\right)$. Taking into account the subgraph $G^{*}\cup T^i\cup T^k$, let us count the necessary crossings in D. It is obvious that we have to deal with the possible existence of a subgraph $T^l\in S_D$ by which the edges of $G^{*}\cup T^i\cup T^k$ can be crossed at most six times. For this reason, suppose that ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)=6$ is fulfilling for some $T^l\in S_D\backslash S_D\left({\mathcal{B}}_2\right)$, $l\ne k$. This enforces that the edge $t_l{v}_4$ of $T^l$ must cross the edge $v_2{v}_3$ of $G^{*}$, which yields ${\mathrm{rot}}_D\left(t_l\right)=\left(124365\right)$. Since the subgraph $F^l$ is identifiable by its rotation ${\mathrm{rot}}_D\left(t_l\right)$, the minimum number of edge crossings of $T^i\cup T^k\cup T^l$ by some subgraph $T^j\in R_D$, $j\ne i$, of at least 11 can be shown by using the properties of cyclic permutations. Over all possible regions of $D(G^{*}\cup T^i\cup T^k\cup T^l)$ the edges of $G^{*}\cup T^i\cup T^k\cup T^l$ are crossed at least 10 times by each subgraph $T^j\in S_D$ with $j\ne k,l$ and ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k\cup T^l,T^j)\ge 9$ is also true for any $T^j\notin R_D\cup S_D$. As ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k\cup T^l)\ge 3+6$, by fixing the subgraph $G^{*}\cup T^i\cup T^k\cup T^l$, we have

$$\begin{gathered} {\mathrm{cr}}_D(G^{*}+D_n)\ge 6⌊\frac{n-3}{2}⌋⌊\frac{n-4}{2}⌋+11(r-1)+10(s-2)+9(n-r-s)+9=6⌊\frac{n-3}{2}⌋⌊\frac{n-4}{2}⌋ \\ +9n+(2r+s)-22\ge 6⌊\frac{n-3}{2}⌋⌊\frac{n-4}{2}⌋+9n+(2⌈\frac{n}{2}⌉+1)-22\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋. \end{gathered}$$

To finish the proof of this subcase, suppose that ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)>6$ holds for any subgraph $T^l\in S_D\backslash S_D\left({\mathcal{B}}_2\right)$, $l\ne k$. Again by summing corresponding values of Table 1, we obtain ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^j)\ge 8$ for any $T^j\in R_D$ with $j\ne i$. The subgraph $F^k$ is represented by the cyclic permutation $\left(154632\right)$, and so ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 1+2+6=9$ for any $T^l\in S_D\left({\mathcal{B}}_1\right)$, $l\ne k$. Moreover, ${\mathrm{cr}}_D(T^i\cup T^k,T^l)\ge 4$ also holds for any $T^l$ with $l\ne i,k$ because four interchanges of adjacent elements of ${\mathrm{rot}}_D\left(t_i\right)$ produce ${\mathrm{rot}}_D\left(t_k\right)$. This forces ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 1+4=5$ for any $T^l\in S_D\left({\mathcal{B}}_2\right)$ and ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k,T^l)\ge 2+4=6$ for any $T^l\notin R_D\cup S_D$. As ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k)\ge 3$, by fixing the subgraph $G^{*}\cup T^i\cup T^k$, we have

$$\begin{gathered} {\mathrm{cr}}_D(G^{*}+D_n)\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+8(r-1)+9(s_1-1)+5s_2+[7(s-s_1-s_2)+6(n-r-s)+3 \\ =6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+6n+(2r+s)+2(s_1-s_2)-14\ge 6⌊\frac{n-2}{2}⌋⌊\frac{n-3}{2}⌋+6n+2⌈\frac{n}{2}⌉+1 \\ +2-14\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋. \end{gathered}$$

Both subcases again confirm a contradiction in D.

iii.

${\mathcal{A}}_1,{\mathcal{A}}_3\notin {\mathcal{M}}_D$ and ${\mathcal{A}}_4\in {\mathcal{M}}_D$. Assume the configuration ${\mathcal{A}}_4$ of some subgraph $F^i$ for $T^i\in R_D$. If the set $S_D\left({\mathcal{B}}_2\right)$ is empty, then the proof proceeds in the same way, like in Subcase 1 with ${\mathcal{A}}_p\in {\mathcal{M}}_D$ for only $p\in \{3,4\}$. Now, let $T^k$ and $T^l$ be some subgraphs from the nonempty sets $S_D\left({\mathcal{B}}_1\right)$ and $S_D\left({\mathcal{B}}_2\right)$, respectively. Over all possible regions of $D(G^{*}\cup T^i\cup T^k\cup T^l)$, each of the $n-3$ subgraphs $T^j$, $j\ne i,k,l$, crosses $G^{*}\cup T^i\cup T^k\cup T^l$ at least 10 times. As ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k\cup T^l)\ge 4+4$, by fixing the subgraph $G^{*}\cup T^i\cup T^k\cup T^l$, we have

$${\mathrm{cr}}_D(G^{*}+D_n)\ge 6⌊\frac{n-3}{2}⌋⌊\frac{n-4}{2}⌋+10(n-3)+8\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋.$$

iv.

${\mathcal{M}}_D=\left\{{\mathcal{A}}_2\right\}$. If the set $S_D\left({\mathcal{B}}_2\right)$ is empty, then the proof also proceeds in the same way, like in Subcase 1 with ${\mathcal{M}}_D=\left\{{\mathcal{A}}_p\right\}$ for only one $p\in \{1,2\}$. Now, let $T^k$ and $T^l$ be some subgraphs from the nonempty sets $S_D\left({\mathcal{B}}_1\right)$ and $S_D\left({\mathcal{B}}_2\right)$, respectively. For $T^i\in R_D$, only using the lower bounds from Table 1, the edges of $G^{*}\cup T^i\cup T^k\cup T^l$ must be crossed by any $T^j\in R_D\cup S_D\left({\mathcal{B}}_1\right)$ with $j\ne i,k$ and $T^j\in S_D\left({\mathcal{B}}_2\right)$ with $j\ne l$ at least 11 and 9 times, respectively. Again, over all possible regions of $D(G^{*}\cup T^i\cup T^k\cup T^l)$, exactly nine crossings on $G^{*}\cup T^i\cup T^k\cup T^l$ can only be achieved by a subgraph, either $T^j\in S_D\left({\mathcal{B}}_2\right)$, $j\ne l$ or $T^j\notin R_D\cup S_D$. As ${\mathrm{cr}}_D(G^{*}\cup T^i\cup T^k\cup T^l)\ge 5+3$, by fixing the subgraph $G^{*}\cup T^i\cup T^k\cup T^l$, we have

$$\begin{gathered} {\mathrm{cr}}_D(G^{*}+D_n)\ge 6⌊\frac{n-3}{2}⌋⌊\frac{n-4}{2}⌋+11(r-1)+11(s_1-1)+9(s_2-1)+10(s-s_1-s_2) \\ +9(n-r-s)+8=6⌊\frac{n-3}{2}⌋⌊\frac{n-4}{2}⌋+9n+(2r+s)+(s_1-s_2)-23 \\ \ge 6⌊\frac{n-3}{2}⌋⌊\frac{n-4}{2}⌋+9n+2⌈\frac{n}{2}⌉+1+1-23\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋. \end{gathered}$$

Both subcases also contradict the assumption (5) in D.

Case 2:${\mathrm{cr}}_D\left(G^{*}\right)=1$, and we consider the subdrawing of $G^{*}$ induced by D given in Figure 1b. The set $R_D$ must be nonempty according to the inequality (7). For subgraphs $T^i\in R_D$, there is only one subdrawing of $F^i\backslash v_2$ identifiable by its subrotation $\left(15634\right)$. The edge $t_i{v}_2$ can be added to two regions of $F^i\backslash v_2$, but the proof proceeds in the same way, like in Subcase 1, with ${\mathcal{A}}_p\in {\mathcal{M}}_D$ for only $p\in \{3,4\}$ for both such possibilities of $F^i$ by adding the edge $t_i{v}_2$.

We have shown that there are at least $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings in each good drawing D of $G^{*}+D_n$. □

4. Two Graphs ${\mathbf{G}}_{\mathbf{1}}$ and ${\mathbf{G}}_{\mathbf{2}}$

In Figure 5, let $G_1$ be the graph on six vertices obtained from $G^{*}$ by adding the new edge $v_1{v}_6$, i.e., $G_1=G^{*}\cup \left\{v_1{v}_6\right\}$. Similarly, let $G_2=G^{*}\cup \left\{v_4{v}_6\right\}$. The good drawing of $G_1+D_n$ with exactly $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings can be obtained if we add the edge $v_1{v}_6$ to the graph $G^{*}$ with no new crossing in Figure 4. The graph $G^{*}+D_n$ is a subgraph of $G_1+D_n$, and therefore, $\mathrm{cr}(G_1+D_n)\ge \mathrm{cr}(G^{*}+D_n)$. Thus, the following result is obvious.

Corollary 1.

$\mathrm{cr}(G_1+D_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ for $n\ge 1$.

Remark that the exact value of the crossing number of the graph $G_1+D_n$ was already obtained by Klešč and Schrötter [27].

For n even, Figure 6 shows the good drawing of the join product $G^{*}+P_n$ with exactly $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings provided by the edges of $K_{6,n}$ cross each other $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋$ times and any subgraph $T^i$ crosses the edges of $G^{*}$ just once.

For n odd, at least 3, Figure 7 shows the good drawing of $G^{*}+P_n$ also with $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋$$+2⌊\frac{n}{2}⌋$ crossings by adding one subgraph $T^{\frac{n+1}{2}}$ by which the edges of each of the $n-1$ graphs $T^i$, $i\ne \frac{n+1}{2}$ are crossed exactly three times, that is,

$$6\frac{n-1}{2}\frac{n-3}{2}+2\frac{n-1}{2}+3(n-1)=6\frac{n-1}{2}\frac{n-1}{2}+2\frac{n-1}{2}.$$

The lower bound is the same, based on Theorem 1, using that $G^{*}+D_n$ is a subgraph of $G^{*}+P_n$.

Corollary 2.

$\mathrm{cr}(G^{*}+P_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ for $n\ge 2$.

The graph $G^{*}$ is a subgraph of $G_2$, and so $\mathrm{cr}(G_2+P_n)\ge \mathrm{cr}(G_2+D_n)\ge \mathrm{cr}(G^{*}+D_n)$. We can also obtain the drawings of $G_2+P_n$ with exactly $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings by adding the edge $v_4{v}_6$ to the graph $G^{*}$ without additional crossings into both Figure 6 and Figure 7.

Corollary 3.

$\mathrm{cr}(G_2+D_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ for $n\ge 1$.

Corollary 4.

$\mathrm{cr}(G_2+P_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ for $n\ge 2$.

5. Three Graphs ${\mathit{H}}^{*}$, ${\mathit{H}}_{\mathbf{1}}$, and ${\mathit{H}}_{\mathbf{2}}$

In Figure 8, let $H^{*}$ be the connected graph of order six consisting of one 4-cycle and two leaves adjacent to two different but not opposite vertices of the 4-cycle. Let $v_3{v}_4{v}_5{v}_6{v}_3$ and $v_1,v_2$ be the vertex notation of the 4-cycle and two leaves of $H^{*}$, respectively. The crossing number of $H^{*}+D_n$ was established by Staš [22].

Theorem 2

(See [22] Theorem 1). $\mathrm{cr}(H^{*}+D_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ for $n\ge 1$.

The same reasoning as for the graph $G^{*}+P_n$ using the drawing of $H^{*}+P_n$ in Figure 9 gives the following result.

Corollary 5.

$\mathrm{cr}(H^{*}+P_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ for $n\ge 2$.

In Figure 10, let $H_1$ be the graph obtained from the planar drawing of $H^{*}$ in Figure 8 by adding the edge $v_1{v}_4$, i.e., $H_1=H^{*}\cup \left\{v_1{v}_4\right\}$. Similarly, let $H_2=H^{*}\cup \{v_1{v}_4,v_2{v}_5\}$. The join products of the graphs $H_1$ and $H_2$ with $P_n$ were already investigated by Draženská [10] and Klešč [1], respectively.

Theorem 3

(See [10] Theorem 1). $\mathrm{cr}(H_1+P_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$ for $n\ge 2$.

Theorem 4

(See [1] Theorem 3.1). $\mathrm{cr}(H_2+P_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$ for $n\ge 2$.

Theorem 5.

$\mathrm{cr}(G_1+P_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$ for $n\ge 2$.

Proof. 

The good drawing of the join product $G_1+P_n$ with exactly $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$ crossings by adding n new edges $v_1{v}_6$, $t_i{t}_{i+1}$, $i=1,\cdots ,n-1$, into the drawing in Figure 4 enforces the required upper border, that is, $\mathrm{cr}(G_1+P_n)\le 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$. To prove the lower border using Corollary 1, we assume a good drawing D of $G_1+P_n$ with $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings. By Corollaries 2 and 5, none of the edges of the 6-cycle of $G_1$ is crossed in D, because otherwise, removing such a crossed edge of the 6-cycle from $G_1$ results in a good drawing of either $G^{*}+P_n$ or $H^{*}+P_n$ with fewer than $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋$ crossings. This also enforces the planar subdrawing of $G_1$ induced by D, and therefore, we can only suppose the subdrawing of the graph $G_1$ given in Figure 5. As there is no crossing on any edge of the path $P_n^{*}$ in D again by Corollary 1, all vertices $t_i$ of $P_n^{*}$ are placed in the same region of $D\left(G_1\right)$. This forces all vertices $t_i$ to be placed in the region of induced subdrawing $D\left(G_1\right)$ with all six vertices of $G_1$ on its boundary, which also yields that the edge $v_3{v}_6$ cannot be crossed by any subgraph $T^i$ in D. As $|R_D|=n$, the considered subdrawing of $G_1\cup T^i$ is represented by the rotation $\left(123456\right)$ and ${\mathrm{cr}}_D(T^i,T^j)\ge 6$ fulfilling, by each other, subgraph $T^j\in R_D$; see Woodall’s results [24]. Thus, we have

$${\mathrm{cr}}_D(G_1+P_n)\ge 6⌊\frac{n-1}{2}⌋⌊\frac{n-2}{2}⌋+6(n-1)+0\ge 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1.$$

The obtained contradiction completes the proof of Theorem 5. □

6. The Crossing Numbers of Join Products of Cycles with Six Graphs of Order Six

Let us suppose a graph G on six vertices with the vertex set $V\left(G\right)=\{v_1,v_2,\cdots ,v_6\}$, and let $t_1,t_2,\cdots ,t_n,t_1$ be the vertex notation of the n-cycle $C_n$ for $n\ge 3$. The join product $G+C_n$ consists of one copy of the graph G, one copy of the cycle $C_n$, and the edges joining each vertex of G with each vertex of $C_n$. Let $C_n^{*}$ denote the cycle as a subgraph of $G+C_n$ induced on the vertices of $C_n$ not belonging to the subgraph G. The subdrawing $D\left(C_n^{*}\right)$ induced by any good drawing D of $G+C_n$ represents some drawing of $C_n$. For the vertices $v_1,v_2,\cdots ,v_6$ of graph G, we denote by $T^{v_i}$ the subgraph induced by n edges joining the vertex $v_i$ with n vertices of $C_n^{*}$. The edges joining six vertices of G with n vertices of $C_n$ form the complete bipartite graph $K_{6,n}$, and so

$$G+C_n=G\cup K_{6,n}\cup C_n^{*}=G\cup \left(\bigcup _{i=1}^6{T}^{v_i}\right)\cup C_n^{*}.$$

(8)

In the proofs of the theorems, the following two statements regarding some restricted subdrawings of $G+C_n$ are useful.

Lemma 5

(See [6] Lemma 2.2). Let D be a good drawing of $D_m+C_n$, $m\ge 2$, $n\ge 3$ in which no edge of $C_n^{*}$ is crossed, and $C_n^{*}$ does not separate the other vertices of the graph. Then, for all $i,j=1,2,\cdots ,m$, two different subgraphs $T^{v_i}$ and $T^{v_j}$ cross each other in D at least $⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋$ times.

Lemma 6

(See [28] Lemma 1). Let G be a graph of order m, $m\ge 1$. In an optimal drawing of the join product $G+C_n$, $n\ge 3$, the edges of $C_n^{*}$ do not cross each other.

Theorem 6.

$\mathrm{cr}(G^{*}+C_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$ for $n\ge 3$.

Proof. 

In both Figure 6 and Figure 7, it is possible to add the edge $t_1{t}_n$ that creates the cycle $C_n^{*}$ on the vertices of $P_n^{*}$ with just two additional crossings, i.e., $C_n^{*}$ is crossed by two edges $v_3{v}_4$ and $v_3{v}_6$ of the graph $G^{*}$. So, $\mathrm{cr}(G^{*}+C_n)\le 6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$. To prove the lower border, let D be a good drawing of $G^{*}+C_n$ with at most $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$ crossings. By Theorem 1, at most, one edge of $C_n^{*}$ can be crossed in D, and we can also suppose that the edges of $C_n^{*}$ do not cross each other using Lemma 6. The induced subdrawing $D\left(C_n^{*}\right)$ divides the plane into two regions with at least four vertices of the 4-cycle of $G^{*}$ in one of them, and so three possible cases may occur:

Case 1: No edge of $C_n^{*}$ crosses any edge of $G^{*}$, that is, all six vertices of $G^{*}$ must be placed in one region of the subdrawing $D\left(C_n^{*}\right)$. As at least five different subgraphs $T^{v_i}$ cannot cross the edges of $C_n^{*}$, any two such different subgraphs $T^{v_i}$ and $T^{v_j}$ cross each other at least $⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋$ times by Lemma 5. This forces at least $\left(\genfrac{}{}{0pt}{}{5}{2}\right)⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋>6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$ crossings in D.

Case 2: Some edge of $C_n^{*}$ crosses the edge $v_1{v}_2$ of $G^{*}$. Five vertices $v_2$, $v_3$, $v_4$, $v_5$, and $v_6$ of $G^{*}$ are placed in one region of $D\left(C_n^{*}\right)$ and any subgraph $T^{v_i}$, $i=2,\cdots ,6$, cross no edge of $G^{*}$. We obtain a contradiction in D using the same estimate as in the previous case.

Case 3: Some edge of $C_n^{*}$ crosses the edge $v_2{v}_3$ of $G^{*}$. Again by Lemma 5, there exist at least

$$\left(\genfrac{}{}{0pt}{}{4}{2}\right)⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+1+{\mathrm{cr}}_D\left(G^{*}\right)+s+2(n-r-s)$$

(9)

crossings in D, where $|R_D|=r$ and $|S_D|=s$. The empty set $R_D$ contradicts the assumption of D for all $n\ge 3$ and we also obtain at least $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$ crossings in the obtained number (9) for all integers n more than 6. For $3\le n\le 6$ and $r\ge 1$, we suppose only two subdrawings of $G^{*}$ presented in Figure 1. Let us first consider the planar subdrawing of $G^{*}$ induced by D given in Figure 1a. For $n=3$, if either $r=2$, $s=1$ or $r=3$, we obtain at least 10 and 12 crossings in D using only some of the values in Table 1, respectively. The similar idea can be applied for $n=4$ if $r\ge 3$. For $r=2$ and $s=2$, if we would like to get the smallest possible number of crossings equal to 17 over the four subgraphs with configurations ${\mathcal{A}}_1$, ${\mathcal{A}}_2$, ${\mathcal{B}}_1$, and ${\mathcal{B}}_2$ (in an effort to obtain their lower bounds in Table 1), we obtain two additional crossings on the edge of $C_n^{*}$ by which the edge $v_2{v}_3$ of $G^{*}$ is crossed. For $n=5$ and $n=6$, it is sufficient, due to (9), to deal only with cases $n=r$, which again, only thanks to the values from Table 1, give us the numbers of crossings contradicting the assumption in D. Finally, assume the nonplanar subdrawing of $G^{*}$ induced by D given in Figure 1b. The number of crossings obtained in (9) confirms a contradiction in D for all n at least 5. For $n=3$ and $n=4$, if either $n=r$ or $n=4$, $r=3$, $s=1$, we can verify the contradicting numbers of crossings in D by a very fast recalculation because the edges of $T^i\cup T^j$ and $T^i\cup T^k$ cross each other at least five and three times for any three different subgraphs $T^i,T^j\in R_D$, $T^k\in S_D$, respectively. The proof of Theorem 6 is done. □

In both Figure 6 and Figure 7 by adding the edge $v_4{v}_6$, it is possible to add the edge $t_1{t}_n$ that creates $C_n^{*}$ on the vertices of $P_n^{*}$ with just two additional crossings. Thus, the result of Corollary 6 is obvious, because $G^{*}+C_n$ is a subgraph of $G_2+C_n$, and so $\mathrm{cr}(G_2+C_n)\ge \mathrm{cr}(G^{*}+C_n)$.

Corollary 6.

$\mathrm{cr}(G_2+C_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$ for $n\ge 3$.

Theorem 7.

$\mathrm{cr}(H^{*}+C_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$ for $n\ge 3$.

Proof. 

The proof proceeds similarly like for the graph $G^{*}+C_n$ in Theorem 6. In Figure 9, adding the edge $t_1{t}_n$ to $P_n^{*}$ offers the good drawing of $H^{*}+C_n$ with $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$ crossings. If we assume a drawing D of $H^{*}+C_n$ with at most $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+1$ crossings, then the result of Theorem 2 forces at most one crossing on the edges of $C_n^{*}$ in D. At least five vertices of $H^{*}$ (that are placed in the same region of the induced subdrawing $D\left(C_n^{*}\right)$) with the corresponding five subgraphs $T^{v_i}$ produce at least $\left(\genfrac{}{}{0pt}{}{5}{2}\right)⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋$ crossings in D. □

Due to Theorem 7, the good drawing of $H^{*}+C_n$ in Figure 11 is optimal. Clearly, we can add both edges $v_1{v}_4$ and $v_2{v}_5$ to the graph $H^{*}$ with no new crossing, and therefore, the crossing numbers of $H_1+C_n$ and $H_2+C_n$ are at most $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$. The result of Corollary 7 is again obvious, because $H^{*}$ is a subgraph of $H_1$, which is also a subgraph of $H_2$, and so $\mathrm{cr}(H_2+C_n)\ge \mathrm{cr}(H_1+C_n)\ge \mathrm{cr}(H^{*}+C_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$.

Corollary 7.

$\mathrm{cr}(H_1+C_n)=\mathrm{cr}(H_2+C_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$ for $n\ge 3$.

Remark that the crossing number of $H_2+C_n$ was already obtained by Klešč [1]. The proof of Theorem 8 can be omitted due to using arguments that are similar to those in the proof of Theorem 5, where the crossings numbers of two graphs $G^{*}+C_n$ and $H^{*}+C_n$ are already given by $6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+2$.

Theorem 8.

$\mathrm{cr}(G_1+C_n)=6⌊\frac{n}{2}⌋⌊\frac{n-1}{2}⌋+2⌊\frac{n}{2}⌋+3$ for $n\ge 3$.

7. Conclusions

We expect that similar special drawings, such as those for the join product $G^{*}+P_n$ in Figure 6 and Figure 7, can be helpful to determine the crossing numbers of the other symmetric graphs on six vertices in the join products with the paths $P_n$. In some proofs for the join products with the cycles $C_n$, we also expect other connection options for the use of two different types of subgraphs, as stated in the proof of Theorem 6. The results of $G^{*}+P_n$, $G_1+P_n$, $H^{*}+P_n$ and $G^{*}+C_n$, $G_1+C_n$, $H^{*}+C_n$ should be also used to establish the crossing numbers of the join products of the completed graph $K_6$ with the paths and the cycles on n vertices. One of the possible ideas for using multiple symmetries (as in the case of $K_6$) is already presented in the proof of Theorem 5.