Přejít k obsahu


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

Citace: [] EKSTEIN, J. Hamiltonovské vlastnosti v mocninách grafů a pakovací barvení grafů. Plzeň : Západočeská univerzita, 2011, 57 s.
Druh: KNIHA
Jazyk publikace: cze
Anglický název: Hamiltonian Properties in the Square of a Graph and Packing Coloring of a Graph
Rok vydání: 2011
Místo konání: Plzeň
Název zdroje: Západočeská univerzita
Autoři: RNDr. Jan Ekstein
Abstrakt CZ: 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 čísla stromů a mřížek. Kapitola 5 se rovněž zabývá pakovacím barvením distančních grafů. Nejprve uvedeme doposud známé výsledky a na závěr kapitoly 5 uvedeme nové výsledky (označené $*$), jejichž důkazy jsou opět v článcích v přílohách.
Abstrakt EN: In the thesis we consider undirected and simple (without loops and multiple edges) graphs. The thesis consists of two main parts: powers of graphs and packing coloring of graphs. One of the basic properties of powers of graphs is given by Fleischner's theorem and Sekanina's theorem (the square of a 2-connected, the third power of a connected graph is hamiltonian, respectively). In Chapter 4 we summarize known results on hamiltonicity, hamiltonian connectivity, traceability, prism hamiltonicity and the existence of a connected even factor in the square of a graph. New results are marked with an asterisk $*$. The concept of packing coloring is motivated by frequency assignment problem in wireless networks. In this context the determination of a packing coloring of trees, lattices and also distance graphs is a quite large field of research. We first summarize known results and in the second part of Chapter 5 we give new results which are also marked with $*$.
Klíčová slova

Zpět

Patička