On the number of spanning trees a planar graph can have

K. Buchin, A. Schulz

Research output: Book/ReportReportAcademic

Abstract

We prove that any planar graph on n vertices has less than 5:2852n 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 2:7156n. As a consequence of the latter the grid size needed to realize a 3d polytope with integer coordinates can be bounded by O(147:7n). To bound the number of spanning trees, we consider the class of directed graphs obtained by taking one outgoing edge at each vertex of the original graph. We probabilistically analyze the dependencies between cycles occurring in these graphs. From this we derive a linear program with infinitely many variables that bounds the number of spanning trees in terms of the degree sequence of the graph. We solve the dual program for a small number of constraints, and then show that the solution obtained also fulfills the remaining constraints.
Original languageEnglish
Publishers.n.
Number of pages18
Publication statusPublished - 2009

Publication series

NamearXiv.org [math.CO]
Volume0912.0712

Fingerprint Dive into the research topics of 'On the number of spanning trees a planar graph can have'. Together they form a unique fingerprint.

  • Cite this

    Buchin, K., & Schulz, A. (2009). On the number of spanning trees a planar graph can have. (arXiv.org [math.CO]; Vol. 0912.0712). s.n.