Name
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 fort≤1 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-connectedK 1.l-free graphs, wherel is fixed. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1007/BF01195323 | Graphs and Combinatorics |
Keywords | Field | DocType |
connected graph,longest path | Graph,Combinatorics,Vertex (geometry),Conjecture,Longest path problem,Mathematics | Journal |
Volume | Issue | ISSN |
9 | 1 | 1435-5914 |
Citations | PageRank | References |
5 | 0.65 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. J. Broersma | 1 | 266 | 33.68 |
| J. van den Heuvel | 2 | 22 | 3.87 |
| H. A. Jung | 3 | 47 | 7.07 |
| H. J. Veldman | 4 | 262 | 44.44 |