Department of Mathematics, University of West Bohemia, Czech Republic
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.
is perhaps the most frequently occurred number in combinatorics. Richard Stanley has collected more than 170 combinatorial objects counted by the Catalan number. Noncrossing partition, which has received great attention recently, is one of these, so called, Catalan objects. Noncrossing partitions are generalized to each finite Coxeter group. In this talk, we will interpret noncrossing partitions of type B in terms of noncrossing partitions of type A. As applications, we can prove interesting properties of noncrossing partitions of type B.