A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10283295" target="_blank" >RIV/00216208:11320/14:10283295 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/s00493-014-2806-z" target="_blank" >http://dx.doi.org/10.1007/s00493-014-2806-z</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00493-014-2806-z" target="_blank" >10.1007/s00493-014-2806-z</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION

Popis výsledku v původním jazyce

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 evenmore. 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 p

Název v anglickém jazyce

A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION

Popis výsledku anglicky

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 evenmore. 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 p

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Combinatorica

ISSN

0209-9683

e-ISSN

—

Svazek periodika

34

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

10

Strana od-do

279-298

Kód UT WoS článku

000338324400002

EID výsledku v databázi Scopus

—