The crossing numbers of Cartesian products of paths with 5-vertex graphs (Q5936042): Difference between revisions

For two graphs obtained from \(K_5\) by removing one edge or two nonadjacent edges it is proved that the crossing number of the Cartesian product of the graph with the path of length \(n\) is \(4n\) and \(3n-1\), respectively. These results complete the list of crossing numbers of Cartesian products of all graphs on five vertices with paths. The list of all presently known crossing numbers of graphs on five vertices with cycles and stars is given. The results presented can be interesting to people working in VLSI layouts.