Mathematics – Combinatorics
Scientific paper
2011-01-27
Mathematics
Combinatorics
IMADA-preprint-math, 25 pages
Scientific paper
We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.
Kriesell Matthias
No associations
LandOfFree
Nonseparating K4-subdivisions in graphs of minimum degree at least 4 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Nonseparating K4-subdivisions in graphs of minimum degree at least 4, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonseparating K4-subdivisions in graphs of minimum degree at least 4 will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-545382