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 non-negative 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+direct-(k~(1/2)) when multiple edges are allowed.
展开▼
机译：受Richter提出的问题和长期存在的Harary-Hill猜想的启发，我们研究了图G的相交数与其圆锥CG的相交数之间的关系。简单的例子表明，对于任何固定的k = cr {G），差cr（CG）-cr（G）可以任意大。在这项工作中，我们有兴趣寻找最小的可能差异，即对于每个非负整数k，找到存在一个交叉数至少为k且图的交叉数为f的圆锥的最小f（k）。 （k）。对于k的小值，当问题限于简单图形时，我们给出f（k）的精确值，并表明当允许有多个边时，f（k）= k + direct-（k〜（1/2）） 。
展开▼
