About: A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: A MINIMUM DEGREE CONDITION FORCING COMPLETE GRAPH IMMERSION Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1007/s00493-014-2806-z
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	P
http://linked.open...avai/riv/aktivity	P(GBP202/12/G061)
http://linked.open...iv/cisloPeriodika	3
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Dvořák, Zdeněk
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	831
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/14:10283295
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	number; minors; conjecture (en)
http://linked.open.../riv/klicoveSlovo	minors number conjecture
http://linked.open...odStatuVydavatele	DE - Spolková republika Německo
http://linked.open...ontrolniKodProRIV	[ED896F119F31]
http://linked.open...i/riv/nazevZdroje	Combinatorica
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	6 (xsd:int)
http://linked.open...vavai/riv/projekt	Center of excellence - Institute for theoretical computer science (CE-ITI)
http://linked.open...UplatneniVysledku	2014
http://linked.open...v/svazekPeriodika	34
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	000338324400002
issn	0209-9683
number of pages	10 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/s00493-014-2806-z
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software