ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 5 Aung, Min, Assumption University, Thailand A Lower bound for the circumference of a graph in terms of connectivity and minimum degree Let G be a simple k-connected graph with the number of vertices v ¿= 3, minimum degree d, and C a longest cycle in G. In 1979, Bondy conjectured that, if the degree sum of any k+1 independent vertices in G is at least v+k(k-1) then G-C contains no path of length k-1. This conjecture has been settled only for the values of k ¡= 8. Our result states that, if G-C has a path of length k-1, then the length of C is at least (1/2)(kd-k(k-1)). (joint work with H. A. Jung, Technische Universitaet Berlin)