Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1371158, author = {Alfaro, Carlos A. and Arroyo, Alan and Derňár, Marek and Mohar, Bojan}, address = {Berlin}, booktitle = {Graph Drawing and Network Visualization - 24th International Symposium, GD 2016}, doi = {http://dx.doi.org/10.1007/978-3-319-50106-2_33}, edition = {LNCS 9801}, editor = {Yifan Hu and Martin Nollenburg}, keywords = {Crossing number; apex graph}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Berlin}, isbn = {978-3-319-50105-5}, pages = {427-438}, publisher = {Springer Verlag}, title = {The Crossing Number of the Cone of a Graph}, year = {2016} }
TY - JOUR ID - 1371158 AU - Alfaro, Carlos A. - Arroyo, Alan - Derňár, Marek - Mohar, Bojan PY - 2016 TI - The Crossing Number of the Cone of a Graph PB - Springer Verlag CY - Berlin SN - 9783319501055 KW - Crossing number KW - apex graph N2 - 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. ER -
ALFARO, Carlos A., Alan ARROYO, Marek DERŇÁR a Bojan MOHAR. The Crossing Number of the Cone of a Graph. In Yifan Hu and Martin Nollenburg. \textit{Graph Drawing and Network Visualization - 24th International Symposium, GD 2016}. LNCS 9801. Berlin: Springer Verlag, 2016, s.~427-438. ISBN~978-3-319-50105-5. Dostupné z: https://dx.doi.org/10.1007/978-3-319-50106-2\_{}33.
|