×

zbMATH — the first resource for mathematics

On vertex-degree restricted paths in polyhedral graphs. (English) Zbl 0946.05047
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.

MSC:
05C38 Paths and cycles
05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI