Mathematics – Combinatorics
Scientific paper
2011-01-13
Mathematics
Combinatorics
Scientific paper
An immersion of a graph $H$ into a graph $G$ is a one-to-one mapping $f:V(H) \to V(G)$ and a collection of edge-disjoint paths in $G$, one for each edge of $H$, such that the path $P_{uv}$ corresponding to edge $uv$ has endpoints $f(u)$ and $f(v)$. The immersion is strong if the paths $P_{uv}$ are internally disjoint from $f(V(H))$. It is proved that for every positive integer $t$, every simple graph of minimum degree at least $200t$ contains a strong immersion of the complete graph $K_t$. For dense graphs one can say even more. If the graph has order $n$ and has $2cn^2$ edges, then there is a strong immersion of the complete graph on at least $c^2 n$ vertices in $G$ in which each path $P_{uv}$ is of length 2. As an application of these results, we resolve a problem raised by Paul Seymour by proving that the line graph of every simple graph with average degree $d$ has a clique minor of order at least $cd^{3/2}$, where $c>0$ is an absolute constant. For small values of $t$, $1\le t\le 7$, every simple graph of minimum degree at least $t-1$ contains an immersion of $K_t$ (Lescure and Meyniel, DeVos et al.). We provide a general class of examples showing that this does not hold when $t$ is large.
DeVos Matt
Dvořák Zdeněk
Fox Jacob
McDonald Jessica
Mohar Bojan
No associations
LandOfFree
Minimum degree condition forcing complete graph immersion 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 Minimum degree condition forcing complete graph immersion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum degree condition forcing complete graph immersion will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-67101