Requiring pairwise nonadjacent chords in cycles

Let ${\cal 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 ${\cal G}_4$ the class of chordal graphs and ${\cal G}_5$ the class of distance-hereditary graphs. I show that $k \ge8$ implies that ${\cal G}_k$ is the class of graphs that have circumference less than $k$. I also characterize ${\cal G}_6$ and ${\cal G}_7$; for instance, a graph is in ${\cal G}_7$ if and only if every hamiltonian subgraph of order $7$ or more is $3$-connected and bipartite.

Motivated by ${\cal G}_4\cap{\cal G}_5$ being the class of ptolemaic graphs, I show that a graph is in ${\cal G}_4\cap{\cal G}_5\cap{\cal G}_6$ if and only if every order-$k$ hamiltonian subgraph has at least $\lfloor k/2 \rfloor$ universal vertices.

Keywords

chord, cycle, chordal graph, distance-hereditary graph, ptolemaic graph

2010 Mathematics Subject Classification

05C75

Full Text (PDF format)

Published 13 August 2013