7
$\begingroup$

$\DeclareMathOperator\cl{cl}$The cyclic edge connectivity $\cl(G)$ is the size of a smallest cyclic edge cut, i.e., a smallest edge cut $F$ such that $G-F$ has two connected components, each of which contains at least one cycle.

In the paper On the cyclic connectivity of planar graphs, Lecture Notes in Math. 303 (1972) 235–242. by M.D. Plummer, Plummer proved the elegant Theorem 4 and leaves an open Question.

Theorem 4. If $G$ is planar and 5-connected, then $\cl(G) \le 13$.

Plummer presented an example of a 5-connected planar graph G with $\cl(G) = 10$. But he claimed that it is unknown whether 5-connected planar graphs with $\cl = 11, 12,$ or $13$ exist.

After searching the literature, I haven't found any related results. Has this question been resolved?

$\endgroup$

1 Answer 1

9
$\begingroup$

Yes, it has been solved.
In 1989 Borodin proved that the maximum cyclic edge connectivity of a 5-connected planar graph is at most 11, improving on Plummer's upper bound of 13. The 11 bound is tight [2].

[1] O.V. Borodin, Solution of Kotzig's and Grünbaum's problems on separability of a cycle in planar graphs, Mat. Zametki 46, 9-12 (1989).
[2] O.V. Borodin and A.O. Ivanova, New results about the structure of plane graphs: a survey (2017).

$\endgroup$
3
  • $\begingroup$ Great, it's a bit unfortunate that reference 1 is in Russian. I wonder if there is an English equivalent proof available. $\endgroup$
    – L.C. Zhang
    Commented May 25 at 10:23
  • 5
    $\begingroup$ English version of [1] is link.springer.com/article/10.1007/BF01139613 $\endgroup$ Commented May 25 at 10:51
  • $\begingroup$ @FedorPetrov and in robust human-readable form: Borodin, O.V. Solution of problems of Kotzig and Grünbaum concerning the isolation of cycles in planar graphs, Mathematical Notes of the Academy of Sciences of the USSR 46, 835–837 (1989), doi.org/10.1007/BF01139613 $\endgroup$ Commented May 26 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.