Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T   of a graph G=(V,E)G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G   for all v∈Vv∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.

Research highlights► Characterization of locally connected spanning tree admissible cographs. ► Characterization of locally connected spanning tree admissible complements of bipartite graphs. ► Every bi-connected doubly chordal graph admits a locally connected spanning tree. ► Linear time algorithms to construct locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs.