Conjectures About Wheels Without One Edge with Paths and Cycles

Abstract

The crossing number $\mathrm{cr}\left(G\right)$ of a graph G is the minimum number of edge crossings over all drawings of G in the plane. The main aim of this paper is to give the crossing numbers of the join products $G^{*}+P_n$ and $G^{*}+C_n$ for the connected graph $G^{*}$ obtained by removing one edge (incident with the dominating vertex) from the wheel $W_5$ on six vertices, and where $P_n$ and $C_n$ are paths and cycles on n vertices, respectively. Finally, we also introduce four new conjectures concerning crossing numbers of the join products of $P_n$ and $C_n$ with $W_m\setminus e$ obtained by removing one edge (of both possible types) from the wheel $W_m$ on $m+1$ vertices.

1. Introduction

The crossing number is one of the basic parameters of a simple graph as it offers certain information about some complexity of the examined graph and, in many cases, determines the difficulty of drawing it [1]. Among the most popular areas in which the minimum number of crossings plays an important role is the implementation of VLSI layout. Integer linear programming can also be used to formulate some exact algorithms to find provably optimal crossing numbers. Implementations of QuickCross heuristics also allow one to find optimal or near-optimal embeddings of many graphs. Minimizing the number of crossovers also has a significant impact on visualizing and understanding complex data [2]. It is evident that drawings of graphs with a lower number of crossings help to create more efficient and of course more reliable (electrical) circuit designs [3]. There are many important graph algorithms defined only for planar graphs, i.e., with a drawing with no crossing edges. This is also one of the reasons why reducing the number of crossings on edges is a frequent problem in planar graph theory [4]. Graphs are also a suitable tool in cartography when depicting various geographical elements such as roads, rivers or political borders. In order to create clearer and more readable maps, any reduction in the number of edge crossings in considered drawings of graphs is highly desirable [5]. In contrast, from Garey and Johnson [6], it is well known that examining the number of crossings of simple graphs is an NP-complete problem. Despite this knowledge, many researchers try to solve this problem at least on some class of graphs. Such a summarization of the known values of crossing numbers for some graph classes has been published thanks to Clancy et al. [7].

Let G be a simple graph (without loops or multiple edges). We use $V\left(G\right)$ and $E\left(G\right)$ to denote the vertex set and the edge set of G, respectively. The used graph terminology is taken from the book [8]. The crossing number of graph G, denoted $\mathrm{cr}\left(G\right)$, is defined as the minimum possible number of edge crossings over all drawings of G in the plane (for the definition of a drawing see Klešč [9]). A drawing with a 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 be a good drawing of graph G. We denote the number of crossings in D by ${\mathrm{cr}}_D\left(G\right)$. Let $G_i$ and $G_j$ be 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)$. For any three mutually edge-disjoint subgraphs $G_i$, $G_j$, and $G_k$ of G by [9], the following equations hold:

$${\mathrm{cr}}_D(G_i\cup G_j)={\mathrm{cr}}_D\left(G_i\right)+{\mathrm{cr}}_D\left(G_j\right)+{\mathrm{cr}}_D(G_i,G_j),$$

(1)

$${\mathrm{cr}}_D(G_i\cup G_j,G_k)={\mathrm{cr}}_D(G_i,G_k)+{\mathrm{cr}}_D(G_j,G_k).$$

(2)

In certain parts of the proofs, we make strong use of Kleitman’s result [10] on crossing numbers for complete bipartite graphs $K_{m,n}$. He showed that

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

(3)

The join product of two graphs $G_i$ and $G_j$, denoted $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 the complete bipartite graph $K_{m,n}$. Let $P_n$ and $C_n$ be the path and the cycle on n vertices, respectively, and let $D_n$ denote the discrete graph (sometimes called empty graph) on n vertices. For a relatively long time, the exact values of the crossing numbers of graphs on at most four vertices in the join product with paths and cycles have been known by Klešč [11,12], and Klešč and Schrötter [13]. Also for this reason, it is desirable to extend this knowledge to all graphs G of order five and six. Several results have already been obtained for $G+P_n$ and $G+C_n$ in the case of a connected graph G on five and six vertices [9,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]. Note that the issue of the Cartesian product and the strong product with paths was partially solved by Klešč et al. in [30,31].

In a good drawing D of some graph G, we say that a cycle Cseparates some two different vertices of the subgraph $G\setminus E\left(C\right)$ if they are contained in different components of ${\mathbb{R}}^2\setminus C$, where ${\mathbb{R}}^2$ means a two-dimensional space. This considered cycle C is said to be a separating cycle of graph G in D, see also Thomassen [32]. In the proofs of this paper, we often use the term “region” in nonplanar subdrawings as well. In that case, crossings are considered to be vertices of the “map”; see again Klešč [9].

Let $G^{*}$ be the connected graph obtained by removing one edge (incident with the dominating vertex) from the wheel $W_5$ on six vertices. This type of edge is referred to as $e_S$ in the following. For any $n\ge 1$, the crossing number of $G^{*}+D_n$ has recently been found by Berežný and Staš [15]. One of the main goals of this paper is to determine both crossing numbers of $G^{*}+P_n$ and $G^{*}+C_n$ described in Theorems 2 and 3, respectively. The paper concludes by giving some new conjectures concerning crossing numbers of the join products of $P_n$ and $C_n$ with $W_m\setminus e$ obtained by removing one edge (of both possible types) from the wheel $W_m$ on $m+1$ vertices. Both conjectures about crossings numbers of $(W_m\setminus e)+D_n$ have already been established in [15]. Of course, we also confirm the correctness of our new hypotheses for some smallest possible values of m and n by using several isomorphisms between graphs mentioned in the last part of Section 4.

2. The Crossing Numbers of ${\mathit{G}}^{*}+{\mathit{P}}_{\mathit{n}}$

Let $G^{*}=(V\left(G^{*}\right),E\left(G^{*}\right))$ be the connected graph on six vertices obtained by removing one edge $e_S$ from the wheel $W_5$, and let also $V\left(G^{*}\right)=\{v_1,v_2,\dots ,v_6\}$. In the rest of the paper, let $v_6$ be the vertex notation of one vertex of degree four (the dominant vertex of $W_5$) in all assumed good subdrawings of $G^{*}$. We denote a cycle $C_5$ induced on the five remaining vertices of $G^{*}$ with degrees two, three, three, three, and three by $C_5^{★}$. Let also $v_1$, $v_2$, $v_3$, $v_4$, and $v_5$ be their vertex notation in the appropriate order of cycle $C_5^{★}$ with ${\mathrm{deg}}_{G^{*}}\left(v_1\right)=2$.

We consider the join product of $G^{*}$ with the discrete graph $D_n$ on n vertices. The graph $G^{*}+D_n$ consists of one copy of $G^{*}$ and n vertices $t_1,t_2,\dots ,t_n$. Any such vertex $t_i$ is adjacent with any vertex of $G^{*}$. Let $T^i$, $1\le i\le n$, denote the subgraph induced by six edges incident with the vertex $t_i$. Since $T^1\cup \cdots \cup T^n$ is isomorphic to $K_{6,n}$, we obtain

$$G^{*}+D_n=G^{*}\cup \bigcup _{i=1}^n{T}^i,$$

(4)

and for all good drawings D of $G^{*}+D_n$, thanks to (1),

$${\mathrm{cr}}_D(G^{*}+D_n)={\mathrm{cr}}_D\left(G^{*}\right)+{\mathrm{cr}}_D\left(\bigcup _{i=1}^n{T}^i\right)+{\mathrm{cr}}_D\left(G^{*},\bigcup _{i=1}^n{T}^i\right).$$

(5)

We denote the path induced on n vertices of $G^{*}+P_n$ not belonging to the subgraph $G^{*}$ by $P_n^{*}$. The path $P_n^{*}$ contains n vertices $t_1,\dots ,t_n$ and $n-1$ edges $t_i{t}_{i+1}$ for $i=1,\dots ,n-1$. As $G^{*}+D_n\subseteq G^{*}+P_n$, we have

$${\mathrm{cr}}_D(G^{*}+P_n)={\mathrm{cr}}_D\left(G^{*}\right)+{\mathrm{cr}}_D\left(\bigcup _{i=1}^n{T}^i\right)+{\mathrm{cr}}_D\left(G^{*},\bigcup _{i=1}^n{T}^i\right)$$

$$+{\mathrm{cr}}_D\left(G^{*}\cup \bigcup _{i=1}^n{T}^i,P_n^{*}\right)+{\mathrm{cr}}_D\left(P_n^{*}\right)$$

for any good drawing D of $G^{*}+P_n$. Determining the crossing numbers of $G^{*}+P_n$ will follow the result of $G^{*}+D_n$ given by Berežný and Staš [15].

Theorem 1 

([15], Theorem 2.6). $\mathrm{cr}(G^{*}+D_n)=6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋$ for $n\ge 1$.

First, let D be a good drawing of $G^{*}+D_n$. The rotation ${\mathrm{rot}}_D\left(t_i\right)$ of a vertex $t_i$ in the drawing D, as the cyclic permutation that records the (cyclic) counter-clockwise order in which the edges leave $t_i$, has been defined by Hernández-Vélez et al. [33] or Woodall [34]. We use the notation $\left(123456\right)$ if the counter-clockwise order 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$. We recall that a rotation is a cyclic permutation. For the purpose of a simpler description, we divide n subgraphs $T^i$ into three mutually disjoint sets of subgraphs depending on the number of crossings with graph $G^{*}$. We denote the set of subgraphs for which ${\mathrm{cr}}_D(G^{*},T^i)=0$ and ${\mathrm{cr}}_D(G^{*},T^i)=1$ by $R_D$ and $S_D$, respectively. Every other subgraph $T^i$ crosses $G^{*}$ at least twice in D. The idea of redistributing $T^i$ subgraphs into three mentioned sets is also preserved in all good drawings of $G^{*}+P_n$ (also for all drawings of $G^{*}+C_n$ in Section 3).

In Figure 1, the edges of $K_{6,n}$ cross each other

$$6\left({\displaystyle \genfrac{}{}{0pt}{}{\lceil \frac{n}{2}\rceil }{2}}\right)+6\left({\displaystyle \genfrac{}{}{0pt}{}{\lfloor \frac{n}{2}\rfloor }{2}}\right)=6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋$$

times, the graph $G^{*}$ is crossed once and twice by each subgraph $T^i$, $i=1,\dots ,\lceil {\displaystyle \frac{n}{2}}\rceil$ on the right side and $T^i$, $i=\lceil {\displaystyle \frac{n}{2}}\rceil +1,\dots ,n$ on the left side, respectively. The path $P_n^{*}$ contributes one crossing to $G^{*}$, and so $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+1$ crossings appear among edges of $G^{*}+P_n$ in this drawing, that is, $\mathrm{cr}(G^{*}+P_n)\le 6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+1$. The aim of Section 2 is to prove that the crossing number of $G^{*}+P_n$ is equal to this upper bound. In the following, we discuss all possible drawings of $G^{*}$ induced by any optimal drawing D of $G^{*}+P_n$.

Lemma 1. 

The edges of $C_5^{★}$ do not cross each other in each optimal drawing D of the join product $G^{*}+P_n$. Moreover, at least five vertices of $G^{*}$ must be located on the boundary of one region $D\left(G^{*}\right)$.

Proof. 

The first part can be easily verified because we can always redraw a crossing of two edges of $C_5^{★}$ trying to obtain a new good drawing of $C_5^{★}$ (with a change in the order of vertices but with a preservation of the incidence of all edges) with fewer edge crossings. This idea has already been presented for $G^{*}+D_n$ by Berežný and Staš [15]. There is only one planar drawing of $G^{*}$ (with respect to isomorphisms), see also Figure 2a. Now, assume an optimal drawing D of $G^{*}+P_n$ with the nonplanar subdrawing $D\left(G^{*}\right)$ and at most four vertices of $G^{*}$ located on a boundary of each region. As the set $R_D\cup S_D$ is empty, ${\mathrm{cr}}_D\left(K_{6,n}\right)\ge 6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋$ thanks to (3) together with ${\sum }_{i=1}^n{\mathrm{cr}}_D(G^{*},T^i)\ge 2n$ enforce more than $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+1$ crossings in D provided that

$${\mathrm{cr}}_D(G^{*}+P_n)\ge {\mathrm{cr}}_D\left(K_{6,n}\right)+{\mathrm{cr}}_D(G^{*},K_{6,n})+{\mathrm{cr}}_D\left(G^{*}\right)$$

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

The drawing from Figure 1 giving the upper bound provides a contradiction with the optimality of D. □

Corollary 1. 

In any optimal drawing D of $G^{*}+P_n$, the set $R_D\cup S_D$ cannot be empty, that is, the subdrawing $D\left(G^{*}\right)$ is isomorphic to one of the nine drawings illustrated in Figure 2.

Theorem 2. 

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

Proof. 

The crossing number of $G^{*}+P_n$ must be at most $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+1$ using the drawing in Figure 1. We prove the reverse inequality by contradiction, and so let us suppose that there is an optimal drawing D of $G^{*}+P_n$ with

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

(6)

Since $\mathrm{cr}(G^{*}+D_n)=6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋$ by Theorem 1, the edges of $G^{*}+P_n$ must be crossed exactly $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋$ times, and no edge of the path $P_n^{*}$ is crossed in D. This also enforces that all vertices $t_i$ of $P_n^{*}$ must be placed in the same region of the considered good subdrawing of $G^{*}$ induced by D. Now, using Corollary 1, we show that a contradiction with assumption (6) can be obtained for all possibilities of obtaining a subgraph $T^i\in R_D\cup S_D$ in D.

Let us first consider the subdrawing $D\left(G^{*}\right)$ given in Figure 2a. As no face is incident with all six vertices of $G^{*}$ in $D\left(G^{*}\right)$, there is no way to obtain a subdrawing of $G^{*}\cup T^i$ for a subgraph $T^i\in R_D$. For $i\in \{1,2,\dots ,n\}$, let $T^i$ be a subgraph from the nonempty set $S_D$, that is, the vertex $t_i$ is placed in the pentagonal region of $D\left(G^{*}\right)$ with the five vertices $v_1$, $v_2$, $v_3$, $v_4$, and $v_5$ of $G^{*}$ on its boundary and the edge $t_i{v}_6$ crosses $G^{*}$ exactly once. There is only one possible subdrawing of $G^{*}\cup T^i$ without the edge $t_i{v}_6$, see also Figure 3.

Because all vertices of $P_n^{*}$ must be placed in the same region of $D\left(G^{*}\right)$, it is easily verified in all five possible regions on three vertices that the edges of $(G^{*}\cup T^i)\setminus t_i{v}_6$ are crossed at least four times by every other subgraph $T^j\setminus t_j{v}_6$, $j\ne i$. Together with at least one crossing on the edge $t_j{v}_6$, the subgraph $T^j$ must cross the edges of $G^{*}\cup T^i$ at least five times. Thus, by fixing the subgraph $G^{*}\cup T^i$ using (3), we obtain

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

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

The same result contrary to (6) can be achieved if we consider the subdrawing of $G^{*}$ induced by D presented in Figure 2b–f.

Let us now discuss the good subdrawing $D\left(G^{*}\right)$ given in Figure 2g. Let the set $R_D$ be nonempty and $T^i\in R_D$, $i\in \{1,2,\dots ,n\}$. The vertex $t_i$ must be located in the hexagonal region of $D\left(G^{*}\right)$ with all six vertices of $G^{*}$ on its boundary, see also Figure 4.

Again one can easily verify over all six considered triangular regions that each subgraph $T^j$, $j\ne i$, must cross the edges of $G^{*}\cup T^i$ at least five times. Then, the same idea as in the previous case also confirms a contradiction with assumption (6) in D. If the set $R_D$ is empty, there are only two possibilities to obtain a subgraph $T^i\in S_D$, $i\in \{1,2,\dots ,n\}$ (the crossed edge of $C_5^{★}$ must be incident with a vertex of degree two). For both subdrawings, we obtain at least five crossings on edges of $G^{*}\cup T^i$ by each remaining subgraph $T^j$, $j\ne i$. Now, the same idea as in the first case again contradicts (6). The same result contrary to (6) can be achieved if we consider both subdrawings $D\left(G^{*}\right)$ given in Figure 2h,i.

Because there is no optimal drawing D of $G^{*}+P_n$ with less than $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+1$ crossings, the proof of Theorem 2 is complete. □

To date, the crossing number of $G^{*}+C_n$ could only be given as a hypothesis. The next section is devoted to this open problem.

3. The Crossing Numbers of ${\mathit{G}}^{*}+{\mathit{C}}_{\mathit{n}}$

Let $t_1,t_2,\dots ,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 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,\dots ,v_6$ of graph $G^{*}$, let $T^{v_i}$ denote the subgraph induced by n edges joining the vertex $v_i$ with n vertices of $C_n^{*}$. The edges joining the vertices of $G^{*}$ with the vertices of $C_n^{*}$ form the complete bipartite graph $K_{6,n}$, and so

$${\mathrm{cr}}_D(G^{*}+C_n)={\mathrm{cr}}_D\left(G^{*}\right)+{\mathrm{cr}}_D\left(\bigcup _{i=1}^n{T}^i\right)$$

$$+{\mathrm{cr}}_D\left(G^{*},\bigcup _{i=1}^n{T}^i\right)+{\mathrm{cr}}_D\left(G^{*}\cup \bigcup _{i=1}^n{T}^i,C_n^{*}\right)+{\mathrm{cr}}_D\left(C_n^{*}\right)$$

for all good drawings D of $G^{*}+C_n$. All three of the following statements concerning some restricted subdrawings of $G+C_n$ are unavoidable to prove the main theorem of Section 3.

Lemma 2 

([11], Lemma 2.2). For $m\ge 2$ and $n\ge 3$, let D be a good drawing of $D_m+C_n$ 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,\dots ,m$, two different subgraphs $T^{v_i}$ and $T^{v_j}$ cross each other in D at least $⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋$ times.

Corollary 2 

([35], Corollary 4). For $m\ge 2$ and $n\ge 3$, let D be a good drawing of the join product $D_m+C_n$ in which the edges of $C_n^{*}$ do not cross each other and $C_n^{*}$ does not separate p vertices $v_1,v_2,\dots ,v_p$, $2\le p\le m$. Let $T^{v_1},T^{v_2},\dots ,T^{v_q}$, $q<p$, be the subgraphs induced on the edges incident with the vertices $v_1,v_2,\dots ,v_q$ that do not cross $C_n^{*}$. If k edges of some subgraph $T^{v_j}$ induced on the edges incident with the vertex $v_j$, $j\in \{q+1,q+2,\dots ,p\}$, cross the cycle $C_n^{*}$, then the subgraph $T^{v_j}$ crosses each of the subgraphs $T^{v_1},T^{v_2},\dots ,T^{v_q}$ at least $⌊{\displaystyle \frac{n-k}{2}}⌋⌊{\displaystyle \frac{(n-k)-1}{2}}⌋$ times in D.

Lemma 3 

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

The crossing numbers of $G^{*}+C_3$ and $G^{*}+C_4$ can be computed using the algorithm located at the website http://crossings.uos.de/ (accessed on 13 September 2024). This algorithm uses the ILP formulation based on Kuratowski subgraphs and thereby determines the crossing numbers of small undirected graphs; see also Chimani and Wiedera [36].

Lemma 4. 

$\mathrm{cr}(G^{*}+C_3)=14$ and $\mathrm{cr}(G^{*}+C_4)=22$.

The proof of Lemma 5 can be easily obtained according to the expected result of the main Theorem 3 of this section and using similar arguments as in the proof of Lemma 1.

Lemma 5. 

For $n\ge 5$, the edges of $C_5^{★}$ do not cross each other in any optimal drawing D of $G^{*}+C_n$. Moreover, if there are at most $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+3$ crossings ind D, then the subdrawing $D\left(G^{*}\right)$ is isomorphic to one of the nine drawings illustrated in Figure 2.

Proof. 

For $n\ge 5$, let D be an optimal drawing of $G^{*}+C_n$. The edges of $C_5^{★}$ do not cross each other using arguments similar to the proof of Lemma 1. If both sets $R_D$ and $S_D$ are empty, then each subgraph $T^i$ crosses edges of $G^{*}$ at least twice. Assuming ${\mathrm{cr}}_D\left(G^{*}\right)\ge 1$ thanks to (3), we obtain a contradiction with at most

$$6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+2n+1>6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+3$$

crossings in D. Since the subdrawing $D\left(G^{*}\right)$ is planar or the set $R_D\cup S_D$ is nonempty, $D\left(G^{*}\right)$ must be isomorphic to one of the nine drawings illustrated in Figure 2. □

Lemma 6. 

For $n\ge 5$, let D be a good drawing of $G^{*}+D_n$ with the nonplanar subdrawing of $G^{*}$ induced by D and one region with all six vertices of $G^{*}$ located on its boundary. If all vertices $t_i$ are placed in such a region and at least one subgraph $T^i$ does not cross edges of $G^{*}$, then there are at least $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+3$ crossings in D.

Proof. 

By Lemma 5, we deal with possible subdrawings of $G^{*}$ induced by D in which the set $R_D$ is nonempty, i.e., there is a region of $D\left(G^{*}\right)$ incident with all six vertices of $G^{*}$. At first, we consider the subdrawing $D\left(G^{*}\right)$ with the vertex notation given in Figure 2g. Let $T^i$ be a subgraph from the nonempty set $R_D$, that is, the subgraph $G^{*}\cup T^i$ is represented by ${\mathrm{rot}}_D\left(t_i\right)=\left(123645\right)$. Because all vertices $t_j$ of $D_n$ lie in the same region of $D\left(G^{*}\right)$, it is easy to verify over only all six possible regions of $D(G^{*}\cup T^i)$ that the edges of $G^{*}\cup T^i$ must be crossed by each of the $n-1$ remaining subgraphs $T^j$ at least five times. Thus, by fixing the subgraph $G^{*}\cup T^i$ using (3), we obtain

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

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

Of course, the same idea of a fixation as in the previous case can be repeated for both possible remaining drawings of $G^{*}$ given in Figure 2h,i with ${\mathrm{rot}}_D\left(t_i\right)=\left(126345\right)$ and ${\mathrm{rot}}_D\left(t_i\right)=\left(162345\right)$, respectively. □

Theorem 3. 

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

Proof. 

The result of Theorem 3 holds for both $n=3$ and $n=4$ based on Lemma 4. The edge $t_1{t}_n$ can be added into the drawing in Figure 1 in such a way that it completes the cycle $C_n^{*}$ on n vertices with exactly three additional crossings, i.e., $t_1{t}_n$ of $C_n^{*}$ crosses three edges $v_3{v}_4$, $v_3{v}_6$, and $v_2{v}_6$ of graph $G^{*}$. Thus, $\mathrm{cr}(G^{*}+C_n)\le 6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+4$, and let us suppose that there is an optimal drawing D of $G^{*}+C_n$ such that

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

(7)

In the rest of the proof, let $I=\{1,2,3,4,5,6\}$. According to Theorem 1 and Lemma 3, there are at most three crossings on the edges of $C_n^{*}$ that do not cross each other, respectively. Now, three possible cases may occur:

Case 1: The edges of $C_n^{*}$ are crossed at most once. There are at least five different considered subgraphs $T^{v_i}$ and $T^{v_j}$ for $i,j\in I$, which cross each other at least $⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋$ times by Lemma 2. It means there are at least $\left({\displaystyle \genfrac{}{}{0pt}{}{5}{2}}\right)⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋$ crossings in D, which confirms a contradiction with the assumption (7).

Case 2: There are just two crossings on the edges of $C_n^{*}$. If ${\mathrm{cr}}_D(G^{*},C_n^{*})=2$ or ${\mathrm{cr}}_D(T^{v_i},C_n^{*})=2$ for exactly one $i\in I$, then the same idea as in Case 1 can be applied. Finally, let ${\mathrm{cr}}_D(T^{v_i},C_n^{*})=1$ and ${\mathrm{cr}}_D(T^{v_j},C_n^{*})=1$ for two distinct $i,j\in I$. Using Lemma 2 and Corollary 2 for $p=6$, $q=4$, $k=1$, we have at least $\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right)⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+(4+4)⌊{\displaystyle \frac{n-1}{2}}⌋⌊{\displaystyle \frac{n-2}{2}}⌋>6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+3$ crossings in D which confirms a contradiction with assumption (7).

Case 3: The edges of $C_n^{*}$ are crossed just three times and we consider three subcases:

(a)

Let ${\mathrm{cr}}_D(G^{*},C_n^{*})=3$. If the cycle $C_n^{*}$ separates only one vertex of graph $G^{*}$ (vertex of degree three), then the same idea as in Case 1 can be also used. Now, let the cycle $C_n^{*}$ separate two vertices of graph $G^{*}$. One vertex $v_1$ of degree two and his neighbor (vertex $v_2$ or $v_5$). Thanks to Lemma 2, together with three crossings on $C_n^{*}$, we have $\left(\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right)+1\right)⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+3$ crossings in D. We need a dispute between at least four more crossings. If $R_D=\varnothing$, we have at least n more crossings, which contradicts the assumption (7). Finally, let $R_D\ne \varnothing$. In this case, ${\mathrm{cr}}_D\left(G^{*}\right)\ge 2$ (see Figure 2), and by Lemma 6, there is at least one vertex $t_m$ located in a different region of $D\left(G^{*}\right)$, $m\in \{1,2,\dots ,n\}$, such that ${\mathrm{cr}}_D(G^{*},T^m)\ge 2$. We also have a contradiction with the assumption (7).

(b)

Let ${\mathrm{cr}}_D(G^{*},C_n^{*})=2$, so ${\mathrm{cr}}_D(T^{v_i},C_n^{*})=1$ for exactly one $i\in I$. If $C_n^{*}$ is not a separating cycle, then the same idea as in Case 1 can be again applied. Now, let $C_n^{*}$ be a separating cycle. It means cycle $C_n^{*}$ separates vertex $v_1$. By Lemma 2, Corollary 2 for $p=5$, $q=4$, $k=1$, together with three crossings on the edges of $C_n^{*}$, we have at least $\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right)⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+4⌊{\displaystyle \frac{n-1}{2}}⌋⌊{\displaystyle \frac{n-2}{2}}⌋+3$ crossings in D, which confirms a contradiction with the assumption (7).

(c)

Let ${\mathrm{cr}}_D(G^{*},C_n^{*})=0$ (a case where ${\mathrm{cr}}_D(G^{*},C_n^{*})=1$ is impossible because $G^{*}$ has no bridge). If ${\mathrm{cr}}_D(T^{v_i},C_n^{*})=3$ for only one $i\in I$, then the same idea as in Case 1 can be again used. Let ${\mathrm{cr}}_D(T^{v_i},C_n^{*})=2$ and ${\mathrm{cr}}_D(T^{v_j},C_n^{*})=1$ for two distinct $i,j\in I$. Then, by Lemma 2, Corollary 2 for $p=6$, $q=4$, $k=1$ and $p=6$, $q=4$, $k=2$, we have at least $\left({\displaystyle \genfrac{}{}{0pt}{}{4}{2}}\right)⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+4⌊{\displaystyle \frac{n-1}{2}}⌋⌊{\displaystyle \frac{n-2}{2}}⌋+4⌊{\displaystyle \frac{n-2}{2}}⌋⌊{\displaystyle \frac{n-3}{2}}⌋>6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+3$ crossings in D, which confirms a contradiction with assumption (7). Finally, let ${\mathrm{cr}}_D(T^{v_i},C_n^{*})=1$, ${\mathrm{cr}}_D(T^{v_j},C_n^{*})=1$, and ${\mathrm{cr}}_D(T^{v_k},C_n^{*})=1$ for three distinct $i,j,k\in I$. For such an index pair $i,j$, the subgraph $T^{v_i}\cup T^{v_j}\cup C_n^{*}$ is isomorphic to $D_2+C_n$. Assume $n-2$ vertices of $C_n^{*}$ incident with the edges of $T^{v_i}$ and $T^{v_j}$ which do not cross $C_n^{*}$. Let us delete all edges of $T^{v_i}$ and $T^{v_j}$ which are not incident with these $n-2$ vertices. The resulting subgraph is homeomorphic to $D_2+C_{n-2}$, and in its subdrawing $D^{\prime }$ induced by D, we obtain ${\mathrm{cr}}_{D^{\prime }}(T^{v_i},T^{v_j})\ge ⌊{\displaystyle \frac{n-2}{2}}⌋⌊{\displaystyle \frac{n-3}{2}}⌋$ thanks to Lemma 2. This fact, together with Lemma 2, Corollary 2 for $p=6$, $q=3$, $k=1$, and three crossings on $C_n^{*}$, gives us $\left({\displaystyle \genfrac{}{}{0pt}{}{3}{2}}\right)⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+(3+3+3)⌊{\displaystyle \frac{n-1}{2}}⌋⌊{\displaystyle \frac{n-2}{2}}⌋+\left({\displaystyle \genfrac{}{}{0pt}{}{3}{2}}\right)⌊{\displaystyle \frac{n-2}{2}}⌋⌊{\displaystyle \frac{n-3}{2}}⌋+3$ crossings, which also contradicts assumption (7).

Because there is no optimal drawing D of $G^{*}+C_n$ with less than $6⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+n+⌊{\displaystyle \frac{n}{2}}⌋+4$ crossings, the proof of Theorem 3 is complete. □

4. Some Consequences of the Main Result

Each wheel $W_m$ on $m+1$ vertices consists of two edge-disjoint subgraphs $C_m^{★}$ and $S_m^{★}$, that is, $E\left(W_m\right)=E\left(C_m^{★}\right)\cup E\left(S_m^{★}\right)$. We distinguish two types of edges of the wheel $W_m$, i.e., let us denote by $e_C$ and $e_S$ any edge of $E\left(C_m^{★}\right)$ and $E\left(S_m^{★}\right)$, respectively. First, we deal with the possibility of deleting one edge $e_S$ from the star $S_m^{★}$ of $W_m$. Staš and Berežný [15] have already claimed the result for the join product with discrete graphs $D_n$, i.e., $\mathrm{cr}(W_m\setminus e_S+D_n)=Z\left(n\right)Z(m+1)+Z(m-1)⌊{\displaystyle \frac{n}{2}}⌋+⌈{\displaystyle \frac{n}{2}}⌉$ for all natural numbers m at least four and n at least one, where by $Z\left(n\right)=⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋$, we mean Zarankiewicz’s number [7]. For all integers $m\ge 3$ and $n\ge 2$, conjectures regarding the crossing number of graphs $W_m+P_n$ with values $Z\left(n\right)Z(m+1)+Z\left(m\right)⌊{\displaystyle \frac{n}{2}}⌋+⌈{\displaystyle \frac{n}{2}}⌉+1$ were given thanks to Staš and Valiska [26]. Now, we are able to postulate the next conjecture.

Conjecture 1. 

$\mathrm{cr}(W_m\setminus e_S+P_n)=Z\left(n\right)Z(m+1)+Z(m-1)⌊{\displaystyle \frac{n}{2}}⌋+⌈{\displaystyle \frac{n}{2}}⌉+1$ for all integers $m\ge 4$ and $n\ge 2$.

For all integers $m\ge 4$, the upper bound for Conjecture 1 can be reached by removing the edge $v_1{v}_{m+1}$ from the drawing in Figure 5, because $e_S=v_1{v}_{m+1}$ is crossed by each subgraph $T^i$ on the left side exactly $\lceil {\displaystyle \frac{m}{2}}\rceil -1$ times. Note that for $m=3$, the optimal drawing of $W_3\setminus e_S+P_n$ with $2⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋+⌊{\displaystyle \frac{n}{2}}⌋+1$ crossings cannot be obtained by removing the edge $v_1{v}_4$ for n odd and at least three. This special situation is first caused by the fact that the wheel $W_3$ is isomorphic to the complete graph $K_4$; see also Klešč and Schrötter [13].

Recently, Su and Huang [27] proved Conjecture 1 for graph $W_4\setminus e_S+P_n$, and the validity for $m=5$ is also confirming by Theorem 2. On the other hand, graph $W_m\setminus e_S+P_2$ contains a subgraph that is a subdivision of graph $W_{m-1}+P_2$. Thus, $\mathrm{cr}(W_{m-1}+P_2)\le \mathrm{cr}(W_m\setminus e_S+P_2)$. The crossing numbers of $W_m+P_2$ are already well known from Staš and Valiska [26].

Theorem 4 

([26], Theorem 5.1). $\mathrm{cr}(W_m+P_2)=Z\left(m\right)+2$ for all integers $m\ge 3$.

Based on the mentioned facts, we can justify further results for the join product of $W_m\setminus e_S$ with the path on two vertices if m is at least four.

Corollary 3. 

$\mathrm{cr}(W_m\setminus e_S+P_2)=Z(m-1)+2$ for all integers $m\ge 4$.

It is easy to see that Corollary 3 also confirms the validity of Conjecture 1 for $n=2$. Similarly, we obtain the following conjecture.

Conjecture 2. 

$\mathrm{cr}(W_m\setminus e_S+C_n)=Z\left(n\right)Z(m+1)+Z(m-1)⌊{\displaystyle \frac{n}{2}}⌋+⌈{\displaystyle \frac{n}{2}}⌉+\lceil {\displaystyle \frac{m}{2}}\rceil +1$ for all integers $m\ge 4$ and $n\ge 3$.

For $m\ge 4$, the upper bound for Conjecture 2 can be reached by removing the edge $e_S=v_1{v}_{m+1}$ from the drawing in Figure 5 and adding the new edge $t_1{t}_n$ such that it completes the cycle $C_n^{*}$ on n vertices with exactly $⌈{\displaystyle \frac{m}{2}}⌉$ additional crossings. Recently, our Conjecture 2 was proved for graph $W_4\setminus e_S+C_n$ by Staš [22]. Theorem 3 also confirms the validity of this conjecture for $m=5$.

Now, let us turn to the possibility of deleting one edge $e_C$ from the cycle $C_m^{★}$ of $W_m$. Staš and Berežný [15] already claimed the result for the join product with discrete graphs $D_n$

$$\mathrm{cr}(W_m\setminus e_C+D_n)=Z\left(n\right)Z(m+1)+⌊{\displaystyle \frac{n}{2}}⌋Z\left(m\right)$$

for all integers $m\ge 3$ and $n\ge 1$. On the assumption of Zarankiewicz’s conjecture saying that $\mathrm{cr}\left(K_{m,n}\right)=⌊{\displaystyle \frac{m}{2}}⌋⌊{\displaystyle \frac{m-1}{2}}⌋⌊{\displaystyle \frac{n}{2}}⌋⌊{\displaystyle \frac{n-1}{2}}⌋$, they established the following:

Theorem 5 

([15], Corollary 3.2). If Zarankiewicz’s conjecture is true, then

$$\mathrm{cr}(W_m\setminus e_C+D_n)=Z\left(n\right)Z(m+1)+⌊{\displaystyle \frac{n}{2}}⌋Z\left(m\right)$$

(8)

holds for all integers $m\ge 3$, $n\ge 1$.

We postulate the following conjecture.

Conjecture 3. 

$\mathrm{cr}(W_m\setminus e_C+P_n)=Z\left(n\right)Z(m+1)+\lfloor {\displaystyle \frac{n}{2}}\rfloor Z\left(m\right)+1$ for all integers $m\ge 3$ and $n\ge 2$.

For all $m\ge 3$, the upper bound for Conjecture 3 can be reached by removing the edge $v_{\lceil {\displaystyle \frac{m}{2}}\rceil }{v}_{\lceil {\displaystyle \frac{m}{2}}\rceil +1}$ from the drawing in Figure 5 because $e_C=v_{\lceil {\displaystyle \frac{m}{2}}\rceil }{v}_{\lceil {\displaystyle \frac{m}{2}}\rceil +1}$ is crossed by each subgraph $T^i$ on the right side exactly once. Similar to the previous case, consequently, by adding the edge $t_1{t}_n$ with just $⌈{\displaystyle \frac{m}{2}}⌉$ additional crossings, we obtain the last conjecture.

Conjecture 4. 

$\mathrm{cr}(W_m\setminus e_C+C_n)=Z\left(n\right)Z(m+1)+\lfloor {\displaystyle \frac{n}{2}}\rfloor Z\left(m\right)+\lceil {\displaystyle \frac{m}{2}}\rceil +1$ for all integers $m,n\ge 3$.

The exact values for the crossing numbers of the join products of $W_3\setminus e_C$, $W_4\setminus e_C$, and $W_5\setminus e_C$ with paths $P_n$ and cycles $C_n$ were given by Klešč and Schrötter [13], Klešč [12], Staš [23], and Staš and Timková [24], respectively, and so the validity of both Conjectures 3 and 4 can be trivially verified for $m=3,4,5$. On the other hand, the graph $W_m\setminus e_C+P_2$ is isomorphic to $P_m+C_3$ because $W_m\setminus e_C\cong K_1+P_m$ and $C_3\cong K_1+P_2$. The crossing numbers of $P_m+C_n$ equal to $Z\left(m\right)Z\left(n\right)+1$ were determined by Klešč [11] for any $m\ge 2$, $n\ge 3$ with $min\{m,n\}\le 6$. Note that graphs $W_m\setminus e_C+P_n$ and $W_n\setminus e_C+P_m$ are isomorphic to each other for all integers m, n at least three due to $W_m\setminus e_C\cong K_1+P_m$ and $W_n\setminus e_C\cong K_1+P_n$. Thus, the next results are obvious and confirming the validity of our Conjecture 3 for $n=2,3,4,5$.

Corollary 4. 

$\mathrm{cr}(W_m\setminus e_C+P_2)=Z\left(m\right)+1$ for $m\ge 3$.

Corollary 5. 

$\mathrm{cr}(W_m\setminus e_C+P_3)=2Z\left(m\right)+⌊{\displaystyle \frac{m}{2}}⌋+1$ for $m\ge 3$.

Corollary 6. 

$\mathrm{cr}(W_m\setminus e_C+P_4)=4Z\left(m\right)+2⌊{\displaystyle \frac{m}{2}}⌋+1$ for $m\ge 3$.

Corollary 7. 

$\mathrm{cr}(W_m\setminus e_C+P_5)=6Z\left(m\right)+4⌊{\displaystyle \frac{m}{2}}⌋+1$ for $m\ge 3$.

Moreover, graph $W_m\setminus e_C+C_n$ is isomorphic to $W_n+P_m$ for all $m,n\ge 3$ using $W_m\setminus e_C\cong K_1+P_m$ and $W_n\cong K_1+C_n$. The crossing numbers of the wheels $W_n$ on four, five, and six vertices in the join product with paths $P_m$ are also given by Klešč and Schrötter [13], Staš and Valiska [26], and Berežný and Staš [14], respectively. Thus, the next results are again obvious and confirm the validity of Conjecture 4 for $n=3,4,5$.

Corollary 8. 

$\mathrm{cr}(W_m\setminus e_C+C_3)=2Z\left(m\right)+m+1$ for $m\ge 3$.

Corollary 9. 

$\mathrm{cr}(W_m\setminus e_C+C_4)=4Z\left(m\right)+m+⌊{\displaystyle \frac{m}{2}}⌋+1$ for $m\ge 3$.

Corollary 10. 

$\mathrm{cr}(W_m\setminus e_C+C_5)=6Z\left(m\right)+m+3⌊{\displaystyle \frac{m}{2}}⌋+1$ for $m\ge 3$.

5. Conclusions

A thorough analysis of all possible drawings of a simple graph $G=\left(V\right(G),E(G\left)\right)$ is one of the main tasks for successfully determining its crossing numbers in the join product with $D_n$, $P_n$ and $C_n$. This form of analysis tends to be much more demanding in cases with an increasing number of edges, especially if $\left|E\right(G\left)\right|\ge 1.5\left|V\right(G\left)\right|$. A lot of drawings can also be solved by sorting them based on the existence or non-existence of a special (separating) subgraph; for more, see also [25].