Title: | Hamiltonovské vlastnosti v iterovaných hranových grafech |
Other Titles: | Hamiltonian properties in iterated line graphs |
Authors: | Kulhánková, Zuzana |
Advisor: | Ekstein Jan, RNDr. Ph.D. |
Referee: | Teska Jakub, RNDr. Mgr. Ph.D. |
Issue Date: | 2024 |
Publisher: | Západočeská univerzita v Plzni |
Document type: | bakalářská práce |
URI: | http://hdl.handle.net/11025/57295 |
Keywords: | hamiltonovská cesta;hamiltonovská kružnice;hamiltonovský cestový index;hamiltonovský index;iterovaný hranový graf. |
Keywords in different language: | hamiltonian cycle;hamiltonian index;hamiltonian path;hamiltonian path index;iterated line graph. |
Abstract: | Nechť $G$ je graf a $k\geq 0$. Potom $k$-tý iterovaný hranový graf je $L^k(G)= L(L^{k-1}(G))$, kde $L^0(G) = G$ a $L^1(G) = L(G)$. Nejmenší přirozené číslo $k$ takové, že iterovaný hranový graf $L^k(G)$ má hamiltonovskou kružnici, respektive cestu, se nazývá hamiltonovský index, respektive hamiltonovský cestový index. Tato bakalářská práce shrnuje doposud známé výsledky existence hamiltonovských kružnic v iterovaných hranových grafech. Výsledky pro hamiltonovské cesty v iterovaných hranových grafech zatím publikované nejsou a v této práci se podařilo ukázat, že hamiltonovský cestový index existuje pro všechny grafy $G$ a~podařilo se určit jeho přesnou hodnotu pro stromy. |
Abstract in different language: | Let $G$ be a graph and $k\geq 0$. The $k$-iterated line graph of a graph $G$ is $L^k(G)= L(L^{k-1}(G))$, where $L^0(G) = G$ and $L^1(G) = L(G)$. The minimum number $k$ such that iterated line graph $L^k(G)$ has hamiltonian cycle, path is called hamiltonian index, hamiltonian path index, respectively. This bachelor's thesis summarizes known results of the existence of hamiltonian cycles in iterated line graphs. The results for hamiltonian paths in iterated line graphs have not been published yet and in this work we also focus on hamiltonian path index and we show that hamiltonian path index exists for all graphs and determine its exact value for trees. |
Rights: | Plný text práce je přístupný bez omezení |
Appears in Collections: | Bakalářské práce / Bachelor´s works (KMA) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
bakalarska_prace_Kulhankova.pdf | Plný text práce | 396,69 kB | Adobe PDF | View/Open |
PV_Kulhankova.pdf | Posudek vedoucího práce | 695,17 kB | Adobe PDF | View/Open |
PO_Kulhankova.pdf | Posudek oponenta práce | 393,84 kB | Adobe PDF | View/Open |
Prubeh_Kulhankova.pdf | Průběh obhajoby práce | 175,45 kB | Adobe PDF | View/Open |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/57295
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.