Hamiltonian Properties in the Square of a Graph and Packing Coloring of a Graph

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F11%3A43899254" target="_blank" >RIV/49777513:23520/11:43899254 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

čeština

Original language name

Hamiltonovské vlastnosti v mocninách grafů a pakovací barvení grafů

Original language description

V předkládané disertační práci se uvažují neorientované a prosté (bez smyček a násobných hran) grafy. Tématy disertační práce jsou grafový operátor mocniny grafu a pakovací barvení grafů. Jedna z důležitých vlastností operace mocniny grafu je dána Fleischnerovou, respektive Sekaninovou větou (druhá mocnina 2-souvislého, respektive třetí mocnina souvislého grafu je hamiltonovská). Je známo, že otázka existence hamiltonovské kružnice ve druhé mocnině grafu je NP-úplný problém. V kapitole 4 uvedeme některédoposud známé podmínky, za kterých má mocnina grafu některou z hamiltonovských vlastností (hamiltonovská souvislost, hamiltonovskost, existence hamiltonovské cesty, hamiltonovský hranol) nebo má mocnina alespoň souvislý sudý faktor, a nové výsledky (označené $*$), jejichž důkazy jsou v článcích v přílohách. Pakovací barvení grafů vzniklo v souvislosti s přiřazováním frekvencí v bezdrátových sítích. V této souvislosti se stalo poměrně studovanou otázkou určení pakovacího chromatického čí

Czech name

Hamiltonovské vlastnosti v mocninách grafů a pakovací barvení grafů

Czech description

V předkládané disertační práci se uvažují neorientované a prosté (bez smyček a násobných hran) grafy. Tématy disertační práce jsou grafový operátor mocniny grafu a pakovací barvení grafů. Jedna z důležitých vlastností operace mocniny grafu je dána Fleischnerovou, respektive Sekaninovou větou (druhá mocnina 2-souvislého, respektive třetí mocnina souvislého grafu je hamiltonovská). Je známo, že otázka existence hamiltonovské kružnice ve druhé mocnině grafu je NP-úplný problém. V kapitole 4 uvedeme některédoposud známé podmínky, za kterých má mocnina grafu některou z hamiltonovských vlastností (hamiltonovská souvislost, hamiltonovskost, existence hamiltonovské cesty, hamiltonovský hranol) nebo má mocnina alespoň souvislý sudý faktor, a nové výsledky (označené $*$), jejichž důkazy jsou v článcích v přílohách. Pakovací barvení grafů vzniklo v souvislosti s přiřazováním frekvencí v bezdrátových sítích. V této souvislosti se stalo poměrně studovanou otázkou určení pakovacího chromatického čí

Type

O - Miscellaneous

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2011

Confidentiality

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