Long paths and cycles in tough graphs |
| |
Authors: | H. J. Broersma J. van den Heuvel H. A. Jung H. J. Veldman |
| |
Affiliation: | (1) Department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands;(2) Fachbereich Mathematik, Technische Universität Berlin, Straße des 17. Juni 135, D-W 1000 Berlin 12, Germany |
| |
Abstract: | For a graphG, letp(G) andc(G) denote the length of a longest path and cycle, respectively. Let (t,n) be the minimum ofp(G), whereG ranges over allt-tough connected graphs onn vertices. Similarly, let (t,n) be the minimum ofc(G), whereG ranges over allt-tough 2-connected graphs onn vertices. It is shown that for fixedt>0 there exist constantsA, B such that (t,n)A·log(n) and (t,n)·log((t,n))B·log(n). Examples are presented showing that fort1 there exist constantsA, B such that (t,n)A·log(n) and (t,n)B· log(n). It is conjectured that (t,n) B·log(n) for some constantB. This conjecture is shown to be valid within the class of 3-connected graphs and, as conjectured in Bondy [1] forl=3, within the class of 2-connectedK1.l-free graphs, wherel is fixed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|