Akademska digitalna zbirka SLovenije - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • A minimum degree condition forcing complete graph immersion
    DeVos, Matt ...
    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.
    Vir: Combinatorica. - ISSN 0209-9683 (Vol. 34, no. 3, 2014, str. 279-298)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2014
    Jezik - angleški
    COBISS.SI-ID - 17210969

    Povezava(-e):

    http://dx.doi.org/10.1007/s00493-014-2806-z

vir: Combinatorica. - ISSN 0209-9683 (Vol. 34, no. 3, 2014, str. 279-298)

loading ...
loading ...
loading ...

Vnos na polico