The Crossing Number of the Cone of a GraphAlfaro, Carlos A. and Arroyo, Alan and Derňár, Marek and Mohar, Bojan (2016) The Crossing Number of the Cone of a Graph. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 427438(Official URL: http://dx.doi.org/10.1007/9783319501062_33). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_33
AbstractMotivated by a problem asked by Richter and by the long standing HararyHill 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+Θ(√k) when multiple edges are allowed.
Actions (login required)
