The Crossing Number of the Cone of a Graph
Carlos A. Alfaro, Alan Arroyo, Marek Derňár, Bojan Mohar · SIAM Journal on Discrete Mathematics · 2018
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 difference $cr(CG)-cr(G)$ can be arbitrarily large for any fixed $k=cr(G)$. In this work, we are interested in finding the smallest possible difference; that is, for each nonnegative integer $k$, find 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+\Theta (\sqrt {k})$ when multiple edges are allowed.