1981/09/01 by Edward Howorka · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #Combinatorics #Mathematics #Euclidean geometry #Graph #Ptolemy's table of chords #Characterization (materials science) #Geodetic datum #Discrete mathematics #Geography #Geometry #Physics
paper · doi:10.1002/jgt.3190050314
openalex publication_date 1981/09/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
Abstract A connected graph G is ptolemaic provided that for each four vertices U i , 1 ≤ i ≤ 4, of G , the six distances d ii = d G (U i , U i ), i ≠ j satisfy the inequality d 12 d 34 ≤ d 13 d 24 + d 14 d 23 (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.