Maximum Linear Forests in Trees

Jian Wang

Published 2017-01-08Version 1

For a graph G, let t(G) (resp. f(G)) be the maximum number of vertices in an induced subgraph of G that is a tree (resp. a forest). Erdos, Saks and Sos show that line graphs of specific trees almost have smallest values of t(G) over all graphs thirty years ago. It is shown that if G is the line graph of tree T, then t(G) equals to the diameter of T. An interesting question is that how large the gap can be between t(G) and f(G) over all line graphs of trees. In this paper, we give lower and upper bounds on f(G) over line graphs of trees with given diameter and line graphs of full k-ary trees. We also construct extremal graphs that achieve these bounds. We find that finding maximum induced forests in line graphs is equivalent to finding maximum linear forests in corresponding original graphs. Although finding maximum linear forests in graphs is NP-hard in general, we proposed a polynomial time algorithm for finding maximum linear forests in trees.