Circumference of essentially 4-connected planar triangulations
Circumference of essentially 4-connected planar triangulations
复制标题
基本上 4 连通平面三角剖分的周长
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Jens M. Schmidt
中科院分区：
文献类型：
--
作者：
Igor Fabrici;J. Harant;Samuel Mohr;Jens M. Schmidt
一个3-连通图G本质上是4-连通的，如果对G的任意3-割S子集V（G），G-S的至多一个分支至少包含两个顶点.本文证明了每个n$顶点的本质4 $-连通极大平面图G$包含一个长度至少为$frac{2}{3}（n+4）$的圈，并且这个界是尖锐的.
A $3$-connected graph $G$ is essentially $4$-connected if, for any $3$-cut $Ssubseteq 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.