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}$?

$\endgroup$
1
  • 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, 2019 at 20:09

0

Reset to default

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.