Boolean distance for graphs

Abstract

The boolean distance between two points x and y of a connected graph G is defined as the set of all points on all paths joining x and y in G (O if X = y). It is determined in terms of the block-cutpoint graph of G, and shown to satisfy the triangle inequality b(x,y)[subset of or equal to] b(x, z)[union or logical sum]b(z,y). We denote by B(G) the collection of distinct boolean distances of G and by M(G) the multiset of the distances together with the number of occurrences of each of them. Then where b is the number of blocks of G. A combinatorial characterization is given for B(T) where T is a tree. Finally, G is reconstructible from M(G) if and only if every block of G is a line or a triangle.