On the crossing number for Kronecker product of a tripartite graph with path

Abstract

The crossing number of a graph G, Cr(G) is the minimum number of edge crossings overall good drawings of G. Among the well-known four standard graph products namely Cartesian product, Kronecker product, strong product and lexicographic product, the one that is most difficult to deal with is the Kronecker product. P.K. Jha and S. Devishetty have analyzed the upper bounds for crossing number of Kronecker product of two cycles in, “Orthogonal Drawings and the Crossing Numbers of the Kronecker product of two cycles”, J. Parallel Distrib. Comput. 72 (2012), 195–204. For any graph G except and K4 of order at most four, the graph is planar. In this paper, we establish the crossing number of Kronecker product of a complete tripartite graph with path and as a corollary, we show that its rectilinear crossing number is same as its crossing number. Also, we give the open problems on the crossing number of above mentioned graphs.

Keywords

• drawing
• crossing number
• kronecker product
• path
• rectilinear crossing number