JavaScript is disabled for your browser. Some features of this site may not work without it.

Boolean distance for graphs

Harary, Frank; Melter, Robert A.; Peled, Uri N.; Tomescu, Ioan

Harary, Frank; Melter, Robert A.; Peled, Uri N.; Tomescu, Ioan

1982

Citation:Harary, Frank, Melter, Robert A., Peled, Uri N., Tomescu, Ioan (1982)."Boolean distance for graphs." Discrete Mathematics 39(2): 123-127. <http://hdl.handle.net/2027.42/24097>

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.