Long cycles in graphs containing a 2factor with many odd components
Heuvel, J. van den (1995) Long cycles in graphs containing a 2factor with many odd components. Discrete Mathematics, 137 (13). pp. 389393. ISSN 0012365X

PDF
199kB 
Abstract:  We prove a result on the length of a longest cycle in a graph on n vertices that contains a 2factor and satisfies d(u)+d(c)+d(w)n+2 for every tiple u, v, w of independent vertices. As a corollary we obtain the follwing improvement of a conjectre of Häggkvist (1992): Let G be a 2connected graph on n vertices where every pair of nonadjacent vertices has degree sum at least nk and assume G has a 2factor with at least k+1 odd components. Then G is hamiltonian. 
Item Type:  Article 
Copyright:  © 1995 Elsevier Science 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/57340 
Official URL:  http://dx.doi.org/10.1016/0012365X(93)E0118N 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page