On vertex-degree restricted paths in polyhedral graphs (Q1970577): Difference between revisions

Given two positive integers \( c, \delta \) and a connected planar graph \( H \), let \( \varphi (c,\delta;H) \) denote the minimum integer such that every \( c \)-connected graph \( G \) of minimum degree \( \geq \delta \) that contains a subgraph isomorphic to \( H \) contains also a subgraph \( H' \) isomorphic to \( H \) for which \( \text{deg}_G(x) \leq \varphi(c,\delta;H) \) for all \( x \in V(H') \). The authors consider two specific classes of connected planar graphs. They show for the class of \( 3 \)-connected planar graphs that \( \varphi(3,4;P_k) = 5k-7 \) for all \( k \)-paths \( P_k \) such that \( k \geq 8 \), and \( \varphi(3,4;H) = \infty \) for all connected planar graphs \( H \) not isomorphic to a \( k \)-path. For the case of \( 4 \)-connected planar graphs, they show that \( \max \{ 5 \lfloor (3k+1)/11 \rfloor + 5, 3k-6 \lceil (3k+1)/11 \rceil + 6 \} \leq \varphi(4,4;P_k) \leq 3k+1 \), for all \( k \geq 4 \). The paper also contains results on the small parameters not covered by the the bounds listed above. The lower bound proofs are constructive and the upper bound ones follow from considering ``counterexamples'' with maximal numbers of edges.