carpathian_2023_39_3_727_743_001

The crossing numbers of join products of seven graphs of order six with paths and cycles


Staš, Michal and Timková, Mária 


Full PDF

carpathian_2023_39_3_727_743

The crossing number \mathrm{cr}(G) 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 of seven graphs on six vertices with paths and cycles on n vertices. The proofs 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. Finally, for m at least three and n=5, we also establish the validity of a conjecture introduced by Sta\v s and Valiska concerning the crossings numbers of the join products of the wheels on m+1 vertices with the paths on n vertices.

 

Additional Information

Author(s)

  Staš, Michal, Timková, Mária 

DOI

https://doi.org/10.37193/CJM.2023.03.12