An infinite class of reach-preservable graphs
Daniel Gagliardi, Marty Lewinter · Networks · 1997
A vertex v of a spanning tree T of a graph G is called reach-preserving if dG(v, w) = dT(v, w) for all w in G. G is called reach-preservable if each of its spanning trees contains at least one reach-preserving vertex. We show that K2,n is reach-preservable. We show that a graph is bipartite if and only if given any pair of vertices, there exists a spanning tree in which both vertices a reach-preserved. ® 1997 Wiley-Liss, Inc.