Factors and cycles in graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F09%3A00501873" target="_blank" >RIV/49777513:23520/09:00501873 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Factors and cycles in graphs
Original language description
A cycle that contains every vertex of a graph is called a hamiltonian cycle and a graph which contains a hamiltonian cycle is called a hamiltonian graph. The problem of the existence of a hamiltonian cycle is closely related to the well known problem ofa travelling salesman. These problems are NP-complete and NP-hard, respectively. While some necessary and sufficient conditions are known, to date, no practical characterization of hamiltonian graphs has been found. There are several ways to generalize the notion of a hamiltonian cycle. In this thesis we make original contributions in two of them, namely, k-walks and r-trestles. In particular, as our main results, we present several new sufficient conditions for the existence of k-walks and r-trestles in a graph. Furthermore we present results dealing with recognizing graphs with an r-trestle and finding them in K_{1;r}-free graphs.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů