A bipartite graph G = ( A , B , E ) is said to be a biconvex bipartite graph if there exist orderings < A in A and < B in B such that the neighbors of every vertex in A are consecutive with respect to < B and the neighbors of every vertex in B are consecutive with respect to < A . A caterpillar is a tree that will result in a path upon deletion of all the leaves. In this paper, we prove that there exists a spanning caterpillar in any connected biconvex bipartite graph . Besides being interesting on its own, this structural result has other consequences. For instance, this directly resolves the burning number conjecture for biconvex bipartite graphs.

Abstract A spanning tree T of a graph G is said to be a tree t‐spanner if the distance between any two vertices in T is at most t times their distance in G. While the complexity of the problem of recognizing whether a graph has a tree t‐spanner is known for any fixed t≠3, the case t = 3 is still open. H.‐O. Le and V. B. Le (1999, Networks, 34(2), 81‐87) have shown that every directed path graph admits a tree 3‐spanner by proposing an algorithm to construct a tree 3‐spanner of a given directed path graph. In this paper, we point out a flaw in their algorithm by producing a directed path graph for which their algorithm fails to produce a tree 3‐spanner although the graph admits a tree 3‐spanner. Furthermore, we show that directed path graphs need not admit tree 3‐spanners in general. Next, we show that directed path graphs of diameter two always admit tree 2‐spanners and hence tree 3‐spanners. Finally, we show that a tree 2‐spanner of a diameter two directed path graph can be constructed in linear time. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 203–210 2007