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 v článcích v přílohách.
Anotace v angličtině
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 *.
Distance graph, hamiltonian connectedness, hamiltonian cycle, powers of graphs, packing coloring of graphs, square lattice.
Rozsah průvodní práce
57s., 16s.,10s., 3s.,12s.
Jazyk
CZ
Anotace
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 v článcích v přílohách.
Anotace v angličtině
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 *.