Let G be a 3-connected planar graph with n vertices and let p(G) be the maximum number of vertices of an induced subgraph of G that is a path. We prove that p(G) ≥ log n/12log log n. To demonstrate the tightness of this bound, we notice that the above inequality implies p(G) ∈ Ω((log_2 n)~(1-ε), where ε is any positive constant smaller than 1, and describe an infinite family of 3-connected planar graphs for which p(G) ∈ O(log n). As a byproduct of our research, we prove a result of independent interest: Every 3-connected planar graph with n vertices contains an induced subgraph that is outerplanar and connected and that contains at least ~3n~(1/2) vertices. The proofs in the paper are constructive and give rise to O(n)-time algorithms.
展开▼
机译:令G为具有n个顶点的3连通平面图,令p(G)为G的诱导子图(即路径)的最大顶点数。我们证明p(G)≥log n / 12log log n。为了证明该边界的紧密性,我们注意到上面的不等式意味着p(G)∈Ω((log_2 n)〜(1-ε),其中ε是小于1的任何正常数,并描述了一个无限的3族p(G)∈O(log n)的连通平面图作为我们研究的副产品,我们证明了一个独立关注的结果:每个具有n个顶点的3连通平面图都包含一个诱导的子图,该子图在平面外并且相互连接且至少包含〜3n〜(1/2)个顶点,本文的证明是建设性的,并产生了O(n)-时间算法。
展开▼