Uncrossed chords of cycles in chordal graphs

Abstract

Strongly chordal graphs are characterized here as being the chordal graphs in which the uncrossed chords of a cycle always form a forest (an "independent set of edges"). Ptolemaic graphs are characterized here as being the chordal graphs in which the uncrossed chords of a cycle always form a matching (a "set of independent edges"). Additional characterizations of ptolemaic graphs involve the number of (un)crossed chords. © 2020 Utilitas Mathematica Publishing Inc.. All rights reserved.