G2
The graph Gk consists of 4k+2 triangles, linked in a ring as in the above picture, together with 2k+1 cross-paths of lengths 1,7,...,6k-5,6k+1,6k-5,...,7,1. The total number of vertices is therefore
| 3(4k+2) + 6( 1 + 2 + ... + k-1 + k + k-1 + ... + 2 + 1 ) | |
| = | 12k+6 + 6k2 |
| = | 6(k+1)2 |
Note that Gk has a Hamilton path (with length β = 6(k+1)2 - 1 ), but has no cycle of length exceeding α = 12k+6 and that α2 < 24β. Thus, α < sqrt(24β) < 5sqrt(β).
The reason that I constructed this example is that the usual example (Voss and Zuluaga) which is used to demonstrate that a 2-connected graph with a path of some length β might have no cycle of length exceeding the ceiling of 2sqrt(β) has a pair of vertices (in fact, many pairs) whose deletion leaves three components. The graph Gk is 2-connected, but the deletion of any two vertices leaves at most two components. (Which is why I call the graph (2,2)-connected.)
An astute reader might see an interesting question here, but I'd like to work on the next step for a while.....
Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
USA
Office: Room 286, Science & Engineering
Phone: (561) 367-3350
Fax: (561) 367-2436
URL: http://www.math.fau.edu/locke/Rel2ConnEx.htm
Last modified July 14, 2003, by S.C. Locke.