On vertex-degree restricted paths in polyhedral graphs (Q1970577): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Erhard Hexel / rank | |||
Property / author | |||
Property / author: Stanlislav Jendroľ / rank | |||
Property / author | |||
Property / author: Hansjoachim Walther / rank | |||
Property / reviewed by | |||
Property / reviewed by: Jajcay, Robert / rank | |||
Revision as of 00:27, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On vertex-degree restricted paths in polyhedral graphs |
scientific article |
Statements
On vertex-degree restricted paths in polyhedral graphs (English)
0 references
18 October 2000
0 references
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.
0 references
\( k \)-connected planar graphs
0 references
subgraphs with restricted degrees
0 references
paths
0 references