Tension continuous maps-Their structure and applications

Kód výsledku v IS VaVaI

RIV/00216208:11320/12:10126092 - isvavai.cz

Výsledek na webu

http://dx.doi.org/10.1016/j.ejc.2011.11.005

DOI - Digital Object Identifier

10.1016/j.ejc.2011.11.005

Jazyk výsledku

angličtina

Název v původním jazyce

Tension continuous maps-Their structure and applications

Popis výsledku v původním jazyce

We consider mappings between edge sets of graphs that lift tensions to tensions. Such mappings are called tension-continuous mappings (shortly TT mappings). The existence of a TT mapping induces a (quasi)order on the class of graphs, which seems to be anessential extension of the homomorphism order (studied extensively, see Hell and Nešetřil (2004) [10]). In this paper we study the relationship of the homomorphism and TT orders. We stress the similarities and the differences in both deterministic and random settings. Particularly, we prove that TT order is universal and investigate graphs for which homomorphisms and TT mappings coincide (so-called homotens graphs). In the course of our study, we prove a new Ramsey-type theorem, which may be of independent interest. We solve a problem asked in [Matt DeVos, Jaroslav Nešetřil, André Raspaud, On edge-maps whose inverse preserves flows and tensions, in: J.A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, J.L. Ramirez Alfonsin (Eds.), Gr

Název v anglickém jazyce

Tension continuous maps-Their structure and applications

Popis výsledku anglicky

We consider mappings between edge sets of graphs that lift tensions to tensions. Such mappings are called tension-continuous mappings (shortly TT mappings). The existence of a TT mapping induces a (quasi)order on the class of graphs, which seems to be anessential extension of the homomorphism order (studied extensively, see Hell and Nešetřil (2004) [10]). In this paper we study the relationship of the homomorphism and TT orders. We stress the similarities and the differences in both deterministic and random settings. Particularly, we prove that TT order is universal and investigate graphs for which homomorphisms and TT mappings coincide (so-called homotens graphs). In the course of our study, we prove a new Ramsey-type theorem, which may be of independent interest. We solve a problem asked in [Matt DeVos, Jaroslav Nešetřil, André Raspaud, On edge-maps whose inverse preserves flows and tensions, in: J.A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier, J.L. Ramirez Alfonsin (Eds.), Gr

Druh

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

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

1M0545: Institut Teoretické Informatiky

Návaznosti

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

Rok uplatnění

2012

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

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

33

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

1207-1225

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—