Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
The Crossing Number of the Cone of a Graph
verfasst von : Carlos A. Alfaro, Alan Arroyo, Marek Derňár, Bojan Mohar
Erschienen in: Graph Drawing and Network Visualization
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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+\varTheta (\sqrt{k})\) when multiple edges are allowed.