Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

25 pages, 27 Figures

Scientific paper

It is known that graphs on n vertices with minimum degree at least 3 have spanning trees with at least n/4+2 leaves and that this can be improved to (n+4)/3 for cubic graphs without the diamond K_4-e as a subgraph. We generalize the second result by proving that every graph with minimum degree at least 3, without diamonds and certain subgraphs called blossoms, has a spanning tree with at least (n+4)/3 leaves, and generalize this further by allowing vertices of lower degree. We show that it is necessary to exclude blossoms in order to obtain a bound of the form n/3+c. We use the new bound to obtain a simple FPT algorithm, which decides in O(m)+O^*(6.75^k) time whether a graph of size m has a spanning tree with at least k leaves. This improves the best known time complexity for MAX LEAF SPANNING TREE.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-554097

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.