The Crossing Number of the Cone of a Graph
| Authors | |
|---|---|
| Year of publication | 2016 |
| Type | Article in Proceedings |
| Conference | Graph Drawing and Network Visualization - 24th International Symposium, GD 2016 |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1007/978-3-319-50106-2_33 |
| Field | Informatics |
| Keywords | Crossing number; apex graph |
| Description | 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+Theta(sqrt(k)) when multiple edges are allowed. |
| Related projects: |