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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\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$
    – Licheng Zhang
    Commented May 25 at 10:23
  • 5
    $\begingroup$ English version of [1] is link.springer.com/article/10.1007/BF01139613 $\endgroup$
    – Fedor Petrov
    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$
    – Peter LeFanu Lumsdaine
    Commented May 26 at 9:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .