On the Maximum Number of Chords in a Cycle of a Graph

L.H. Clark1, T.D. Porter2
1
2Southern Illinois University at Carbondale Carbondale, IL 62901

Abstract

We give an exponential lower bound for the maximum number of chords in a cycle of a graph \(G\) in terms of the minimum degree of \(G\) and the girth of \(G\). We also give regular graphs having no small cycles where the maximum number of chords possible in any cycle of the graph is approximately the fourth power of our lower bound. An immediate consequence is a recent result of Ali and Staton.