School Seminars and Colloquia

Trestles and walks in graphs

ORSUM Seminar

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