THE i-CHORDS OF CYCLES AND PATHS

An i-chord of a cycle or path is an edge whose endpoints are a distance i >= 2 apart along the cycle or path. Motivated by many standard graph classes being describable by the existence of chords, we investigate what happens when i-chords are required for specific values of i. Results include the following: A graph is strongly chordal if and only if, for i. {4, 6}, every cycle C with vertical bar V(C)vertical bar >= i has an (i/2)-chord. A graph is a threshold graph if and only if, for i is an element of{4, 5}, every path P with vertical bar V (P)vertical bar >= i has an (i-2)-chord.