Abstract
An immersion of a graph H into a graph G is a one-to-one mapping f: V (H) -> 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 Ht, 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, 1a parts per thousand currency signta parts per thousand currency sign7, every simple graph of minimum degree at least t-1 contains an immersion of K (t) (Lescure and Meyniel [13], DeVos et al. [6]). We provide a general class of examples showing that this does not hold when t is large.