Journal of Graph Theory · 1981 · 105 citations · 5 references
Natural SciencesComputer ScienceMathematicsCombinatoricsGeomaticsGeometryGeometric GraphsGraph TheoryCliquesGeometric Graph Theory
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.
5
Dominic Welsh · Bulletin of the London Mathematical Society · 1974 · 1.1K citations
A characterisation of rigid circuit graphs
Peter Buneman · Discrete Mathematics · 1974 · 323 citations