# Trestles and walks in graphs

*by Dr Roman Kuzel*

*Institution:*Department of Mathematics, University of West Bohemia, and Institute for Theoretical Computer Science, Charles University Univerzitni 8, 306 14 Plzen, Czech Republic

*Date: Fri 26th May 2006*

*Time: 1:05 PM*

*Location: Room 213, Department of Mathematics and Statistics, Richard Berry building, University of Melbourne.*

*Abstract*: 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. A graph G is called K1,r-free if G has no K1,r as an induced subgraph. This concept can be viewed as an interesting variation on the notion of hamiltonian 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 Ã¢â€°Â¥ 1 is an integer. We show that every 2-connected K1,r-free graph has an r-trestle and that every bridgeless graph of maximum degree Ã¢Ë†â€ has a spanning