Circumference of essentially 4-connected planar triangulations

Authors

  • Igor Fabrici
  • Jochen Harant
  • Samuel Mohr
  • Jens Schmidt

DOI:

https://doi.org/10.7155/jgaa.v25i1.2350

Keywords:

circumference , long cycle , triangulation , essentially 4-connected , planar graph

Abstract

A $3$-connected graph $G$ is essentially $4$-connected if, for any $3$-cut $S\subseteq V(G)$ of $G$, at most one component of $G-S$ contains at least two vertices. We prove that every essentially $4$-connected maximal planar graph $G$ on $n$ vertices contains a cycle of length at least $\frac{2}{3}(n+4)$; moreover, this bound is sharp.

Downloads

Download data is not yet available.

Downloads

Published

2021-01-01

How to Cite

Fabrici, I., Harant, J., Mohr, S., & Schmidt, J. (2021). Circumference of essentially 4-connected planar triangulations. Journal of Graph Algorithms and Applications, 25(1), 121–132. https://doi.org/10.7155/jgaa.v25i1.2350

Issue

Section

Articles

Categories