KAIST Discrete Math Seminar

Hamiltonian cycle in a graph G is a cycle, which contains every vertex of the graph G. The problem of existence of a hamiltonian cycle in a graph is a well known NP-complete problem. While some theoretical necessary and sufficient conditions are known, to date, but no practical characterization of hamiltonian graphs has been found. There are several ways how to generalize the notion of a hamiltonian cycle.

For any integer r>1, an r-trestle is a 2-connected graph F with maximum degree ∆(F)≤ r. We say that a graph G has an r-trestle if G contains a spanning subgraph which is an r-trestle. This concept can be viewed as an interesting variation on the notion of Hamilton cycle. Another such variation is a concept of k-walks, where a k-walk in a graph G is a closed spanning walk visiting each vertex at most k times, where k is a positive integer.

We present several results and problems concerning mainly with k-walks and r-trestles and relations between them.