The subgraph homeomorphism problem for small wheels
From MaRDI portal
The author quickly shows that every vertex of degree at least 4 in a 3- connected graph is the ``hub of a subdivision of a wheel with four spokes. Using this result he then proves, by extensive case analysis, that a graph G contains a subdivision of a 5-spoked wheel if it is 3- connected, has a vertex v of degree 5 and a cycle of length at least 5 that does not contain v, and does not have a set E of three edges such that each component of G-E has more than one vertex.
Recommendations
Cites work
- A note on primitive skew curves
- Functions of Bounded Second Variation and Stieltjes-Type Integrals
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Parallel concepts in graph theory
- Some Theorems on Abstract Graphs
- The subgraph homeomorphism problem
- Topology of series-parallel networks
Cited in
(9)- Structure and recognition of graphs with no 6-wheel subdivision
- The existence of homeomorphic subgraphs in chordal graphs
- The characterization of graphs with no 2-connected spanning subgraph of \(V_8\) as a minor
- Graphs with no 7-wheel subdivision
- A minimum degree condition for wheels
- The structure of graphs not topologically containing the Wagner graph
- Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
- Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
- Typical subgraphs of 3- and 4-connected graphs
This page was built for publication: The subgraph homeomorphism problem for small wheels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1117247)
