| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

7. Crossing number of cones

    1. Crossing number of cones

          Let $\phi(k) = \text{min}\{\text{cr}(\text{Cone(G)}) - \text{cr}(G)\}$ where the minimum is taken over all graph $G$ with $\text{cr}(G) = k$ and $\text{Cone}(G)$ is the graph obtained by adding a vertex and connected it to all vertices of $G$. The exactly value of $\phi(k)$ is known for $k \leq 7$ and conjectured that $\phi(k) = (1+ o (1)) \sqrt{2} k^{\frac{3}{4}}$.

      Add remark

      Problem 7.1.

      [Carlos A. Alfaro] Compute $\phi(k)$ for $k \geq 8$.
          Note: 1. It is known that $\sqrt{k/2} \leq \phi(k) \leq O(k^{3/4})$ where the upper bound is by considering complete graphs. 2. The same problem may be asked under the setting that the graphs are drawn on surfaces, or may be asked for multigraphs.

      Reference: C.A. Alfaro, A. Arroyo, M. Dernar, B. Mohar. The crossing number of the cone of a graph. SIAM Journal on Discrete Mathematics 32.3 (2018): 2080–2093.

      Z. Ding, Y. Huang. A Note on the Crossing Number of the Cone of a Graph. Graphs and Combinatorics 37 (2021): 2351–2363.

          Cite this as: AimPL: Albertson conjecture and related problems, available at http://aimpl.org/albertson.