# On the Crossing Numbers of the Join Products of Six Graphs of Order Six with Paths and Cycles  
[PERSON]  
1 Faculty of Electrical Engineering and Informatics, Technical University of Kosice, 042 00 Kosice, Slovakia; michal.stas@tuke.  
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(G_{i})\) and \(V(G_{j})\). For \(|V(G_{i})|=m\) and \(|V(G_{j})|=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 [PERSON] [6, 7], and [PERSON] [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, \(\operatorname{cr}(G+P_{n})\) and \(\operatorname{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\left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor+2 \left\lfloor\frac{n}{2}\right\rfloor\) 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. Note that we are unable to establish \(\operatorname{cr}(G^{*}+D_{n})\) using the methods presented in [21] because there is a possibility to obtain a subgraph \(T^{j}\) with \(\operatorname{cr}_{D}(T^{i},T^{j})=1\) and \(\operatorname{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 \(\operatorname{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], StaS proved the crossing number of \(H^{*}+D_{n}\) for \(n\geq 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 \(\operatorname{cr}(G^{*}+P_{n})\) and \(\operatorname{cr}(H^{*}+P_{n})\) help us to state \(\operatorname{cr}(G_{1}+P_{n})\) as the result of Theorem 5, thanks to multiple symmetries of the graph \(G_{1}\). \(\operatorname{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.