Spanning trees and orientations of graphs

A conjecture of Merino and Welsh says that the number of spanning trees $\tau(G)$ of a loopless and bridgeless multigraph $G$ is always less than or equal to either the number $a(G)$ of acyclic orientations, or the number $c(G)$ of totally cyclic orientations, that is, orientations in which every edge is in a directed cycle. We prove that $\tau(G) \leq c(G)$ if $G$ has at least $4n$ edges, and that $\tau(G) \leq a(G)$ if $G$ has at most $16n/15$ edges. We also prove that $\tau(G) \leq a(G)$ for all multigraphs of maximum degree at most $3$ and consequently $\tau(G) \leq c(G)$ for any planar triangulation.

Keywords

spanning trees, acyclic orientations, cyclic orientations of graphs

2010 Mathematics Subject Classification

05C05, 05C07, 05C20, 05C38

Full Text (PDF format)

Published 1 January 2010