Circumference of Triangle-Free and Regular Graphs

摘要

Dirac-type questions concerning triangle-free graphs and regular graphs are considered. It is shown that for any longest cycle C in a two-connected, triangle-free graph G, the remaining graph G-C has at most one edge provided (G) less than or = 6 delta (delta = minimum valence). Any longest cycle in a two-connected, delta-regular, bipartite graph on at most 6 delta-6 vertices is shown to be dominating. A variation of the Hopping lemma is introduced, to estimate C(G) for regular graphs. A lower bound for the circumference of a three-connected, delta-regular, bipartite graph is given. It is shown that a two-connected, delta-regular, bipartite graph on at most 5 delta-8 vertices is Hamiltonian.