Requiring pairwise nonadjacent chords in cycles
Terry A. McKee · Journal of Combinatorics · 2013
Let G k be the class of graphs for which every cycle of length k or more has at least k -3 pairwise nonadjacent chords.This makes G 4 the class of chordal graphs and G 5 the class of distance-hereditary graphs.I show that k ≥ 8 implies that G k is the class of graphs that have circumference less than k.I also characterize G 6 and G 7 ; for instance, a graph is in G 7 if and only if every hamiltonian subgraph of order 7 or more is 3-connected and bipartite.Motivated by G 4 ∩ G 5 being the class of ptolemaic graphs, I show that a graph is in G 4 ∩ G 5 ∩ G 6 if and only if every order-k hamiltonian subgraph has at least k/2 universal vertices.