When every k ‐cycle has at least f ( k ) chords

It is easy to characterize chordal graphs by every k ‐cycle having at least f ( k ) = k − 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f ( k ) = 2⌊( k − 3)/2⌋, and of the graphs whose blocks are trivially perfect using f ( k ) = 2 k − 7. These three functions f ( k ) are optimum in that each class contains graphs in which every k ‐cycle has exactly f ( k ) chords. The functions 3⌊( k − 3)/3⌋ and 3 k − 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k ‐cycles are replaced with k ‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011