The Crossing Number of the Cone of a Graph


Recommended citation: Alfaro, C.A., Arroyo, A., Derňár, M. and Mohar, B., 2018. The Crossing Number of the Cone of a Graph. SIAM Journal on Discrete Mathematics, 32(3), pp.2080-2093.

Motivated by a problem asked by Richter and by the long standing Harary–Hill conjecture, we study the relation between the crossing number of a graph and the crossing number of its cone , the graph obtained from by adding a new vertex adjacent to all the vertices in . Simple examples show that the difference $cr(CG)-cr(G)$ can be arbitrarily large for any fixed . In this work, we are interested in finding the smallest possible difference; that is, for each nonnegative integer , find the smallest for which there exists a graph with crossing number at least and cone with crossing number . For small values of , we give exact values of when the problem is restricted to simple graphs and show that when multiple edges are allowed.