On the Crossing Numbers of Cartesian Product of a 6-vertices Graph with Paths
Huang Yuan-qiu · Journal of Shanxi Normal University · 2007
Determining the crossing numbers of graphs is NP-complete.Because of the complexity of the problem,there are a few exact results on the crossing numbers of graphs.In this paper,we first consider a good drawing of F×Pn and through this find Cr(F×Pn)≤4n good drawing;then we proved that Cr(F×Pn)≥4n by induction.so we assert that Cr(F×Pn)≥4n.