THE CROSSING NUMBER OF THE CONE OF A GRAPH

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 G and the crossing number of its cone CG, the graph obtained from G by adding a new vertex adjacent to all the vertices in G. Simple examples show that the di ff erence cr (CG) - cr (G) can be arbitrarily large for any fi xed k = cr (G). In this work, we are interested in fi nding the smallest possible di ff erence; that is, for each nonnegative integer k, fi nd the smallest f (k) for which there exists a graph with crossing number at least k and cone with crossing number f (k). For small values of k, we give exact values of f (k) when the problem is restricted to simple graphs and show that f (k) = k + circle minus(root k) when multiple edges are allowed.