Contents Online

# Journal of Combinatorics

## Volume 4 (2013)

### Number 3

### Requiring pairwise nonadjacent chords in cycles

Pages: 357 – 372

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n3.a5

#### Author

#### Abstract

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