Extremal Problems Concerning Cycles in Graphs
by
Tri Atmojo Kusmayadi
Curtin University of Technology, GPO Box U1987, Perth 6845, Western Australia
Coauthors: Louis Caccetta (Curtin University of Technology, Perth, Western Australia)

Let G be a connected graph with connected complement [`(G)]. The circumference c(G) of G is defined as the length of the longest cycle in G; if G has no cycles we define c(G) = \infty. We consider the following problem : Given c(G) and c([`(G)]) determine the maximum number of edges of G and characterize the extremal graphs. Results for specific c(G) and c([`(G)]) will be presented. The above can be considered as a variation of the Nordhaus-Gaddum type problem.

Date received: November 6, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-34.