A short proof of a characterization of strongly chordal graphs

A graph G is chordal if every induced subgraph of G contains a simplicial vertex (a vertex whose neighborhood is a clique). A graph G is strongly chordal if every induced subgraph of G contains a simple vertex, where a vertex is simple if the closed neighborhoods of its neighbors form a chain under inclusion. In 1983, Farber gave several characterizations of strongly chordal graphs, including the following: A graph is strongly chordal if it is chordal and contains no trampoline as an induced subgraph, where a trampoline (or a sun) is a graph on 2k vertices (k is at least 3) consisting of a 2k-cycle and a clique on the even vertices of the cycle (the odd-indexed vertices form a stable set). We present a short proof of this theorem.

Joint work with Jacent Tokaz and Douglas B. West