On vertex-degree restricted paths in polyhedral graphs
type: Item
instance of: scholarly article
title: On vertex-degree restricted paths in polyhedral graphs
zbMATH Open document ID: 0946.05047
DOI: 10.1016/S0012-365X(99)00209-5
author: Igor Fabrici
author: Erhard Hexel
author: Stanislav Jendroľ
author: Hansjoachim Walther
published in: Discrete Mathematics
publication date: 2000-10-18T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1420214
zbMATH Keywords: \( k \)-connected planar graphs
zbMATH Keywords: subgraphs with restricted degrees
zbMATH Keywords: paths
reviewed by: Robert Jajcay
MaRDI profile type: Publication
Recommended article: On vertex-degree restricted subgraphs in polyhedral graphs
Recommended article: Paths with restricted degrees of their vertices in planar graphs
Recommended article: Q4518401
Recommended article: On the complexity of vertex-disjoint length-restricted path problems
Recommended article: On cardinality constrained cycle and path polytopes
Recommended article: Subgraphs with restricted degrees of their vertices in planar graphs
Recommended article: On short paths through prescribed vertices of a graph
Recommended article: Q4839195
Recommended article: A polyhedral theory on graphs
Recommended article: On paths avoding forbidden pairs of vertices in a graph
description: scientific article; zbMATH DE number 1420214