Attributes | Values |
---|
rdf:type
| |
rdfs:seeAlso
| |
Description
| - 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.
- 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. (en)
|
Title
| - A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION
- A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION (en)
|
skos:prefLabel
| - A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION
- A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION (en)
|
skos:notation
| - RIV/00216208:11320/14:10283295!RIV15-GA0-11320___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| |
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216208:11320/14:10283295
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - number; minors; conjecture (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| - DE - Spolková republika Německo
|
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| |
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| - Dvořák, Zdeněk
- DeVos, Matt
- Mohar, Bojan
- Fox, Jacob
- McDonald, Jessica
- Scheide, Diego
|
http://linked.open...ain/vavai/riv/wos
| |
issn
| |
number of pages
| |
http://bibframe.org/vocab/doi
| - 10.1007/s00493-014-2806-z
|
http://localhost/t...ganizacniJednotka
| |