On the number of spanning trees a planar graph can have

Details On the number of spanning trees a planar graph can have On the number of spanning trees a planar graph can have

2009-12-03

arxiv.org/abs/0912.0712v2

Mathematics

Combinatorics

Computations in Mathematica included as supplemental material

Scientific paper

We prove that any planar graph on $n$ vertices has less than $O(5{.}2852^n)$ spanning trees. Under the restriction that the planar graph is 3-connected and contains no triangle and no quadrilateral the number of its spanning trees is less than $O(2{.}7156^n)$. As a consequence of the latter the grid size needed to realize a 3d polytope with integer coordinates can be bounded by $O(147.{7}^n)$. Our observations imply improved upper bounds for related quantities: the number of cycle-free graphs in a planar graph is bounded by $O(6.4884^n)$, the number of plane spanning trees on a set of $n$ points in the plane is bounded by $O(158.6^n)$, and the number of plane cycle-free graphs on a set of $n$ points in the plane is bounded by $O(194{.}7^n)$.

Affiliated with

Also associated with

No associations

Rating

On the number of spanning trees a planar graph can have 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 On the number of spanning trees a planar graph can have, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of spanning trees a planar graph can have will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-517995