Maximum Leaf Spanning Tree Problem for Grid Graphs

Ben P. C. Li1, M. Toulouse2
1Department of Computer Science University of Manitoba Winnipeg, Manitoba Canada R3T 2N2
2 CIRRELT Université de Montréal Montréal, Québec Canada H38T 1J4

Abstract

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.