The complexity of the maximum leaf spanning tree problem for grid graphs is currently unknown. We determine the maximum number of leaves in a grid graph with up to \(4\) rows and with \(6\) rows. Furthermore, we give some constructions of spanning trees of grid graphs with a large number of leaves.
Citation
Ben P. C. Li, M. Toulouse. Maximum Leaf Spanning Tree Problem for Grid Graphs[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 073. 181-193. .