A characterization of ptolemaic graphs
Edward Howorka · Journal of Graph Theory · 1981
Abstract A connected graph G is ptolemaic provided that for each four vertices Ui, 1 ≤ i ≤ 4, of G, the six distances dii = dG (Ui, Ui), i ≠ j satisfy the inequality d12d34 ≤ d13d24 + d14d23 (shown by Ptolemy to hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). in the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only iffor each nondisjoint cliques P, Q of G, their intersection is a cutset of G which separates P‐Q and Q‐P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.