Spanning trees with many leaves: new extremal results and an improved FPT algorithm

P.S. Bonsma

Research output: Book/ReportReportProfessional

34 Downloads (Pure)

Abstract

We present two lower bounds for the maximum number of leaves in a spanning tree of a graph. For connected graphs without triangles, with minimum degree at least three, we show that a spanning tree with at least (n+4)/3 leaves exists, where n is the number of vertices of the graph. For connected graphs with minimum degree at least three, that contain D diamonds induced by vertices of degree three (a diamond is a K4 minus one edge), we show that a spanning tree exists with at least (2n-D+12)/7 leaves. The proofs use the fact that spanning trees with many leaves correspond to small connected dominating sets. Both of these bounds are best possible for their respective graph classes. For both bounds simple polynomial time algorithms are given that find spanning trees satisfying the bounds. The second bound is used to find a new fastest FPT algorithm for the Max-Leaf Spanning Tree problem. This problem asks whether a graph G on n vertices has a spanning tree with at least k leaves. The time complexity of our algorithm is f(k)g(n), where g(n) is a polynomial, and f(k) Î O(8.12k).
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Faculty of Mathematical Sciences
Number of pages53
Publication statusPublished - Feb 2006

Publication series

NameMemorandum Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
No.1793
ISSN (Print)0169-2690

Keywords

  • MSC-05C35
  • MSC-05C69
  • MSC-05C85
  • METIS-237578
  • IR-66582
  • EWI-8056

Cite this