5
$\begingroup$

Suppose that I have a graph $G=(V,E)$ with a known crossing number, say $n=cr(G)$. I would like to show that the graph $G'=(V,E\cup e')$ obtained by adding an edge $e'$ to $G$ that was not previously in it satisfies the relation:

$$cr(G')\leq cr(G)+1.$$

Is this true in general? Or at least for the family of complete graphs $K_{m,n}$?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Can't be true in general if I'm understanding correctly: crossing number is at least $e^3 / (29 v^2)$ when $e > 7v$ from the crossing number inequality (wikipedia; $e$ is # edges, $v$ is # vertcies). Pick say $v=20, e = 141$. Start with a graph on $v$ nodes and 0 edges. Add $e$ edges one-by-one. Overall crossing number increased from 0 to $e^3 / (29v^2) \ge 241 > 141 = e$. So crossing number must have increased by 2 at least once. Not sure about the $K_{m, n}$ case. $\endgroup$ – xmq May 9 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.