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

AKCE International Journal of Graphs and Combinatorics

N. Shanthini¹  J. Baskar Babujee¹ 

[1] Anna University;

关键词: drawing;    crossing number;    kronecker product;    path;    rectilinear crossing number;   

DOI  :  10.1016/j.akcej.2019.08.004

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown