On vertex-degree restricted paths in polyhedral graphs (Q1970577): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
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 | |||
Property / author | |||
Property / author: Erhard Hexel / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Stanlislav Jendroľ / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Hansjoachim Walther / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jajcay, Robert / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 06:24, 5 March 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