Journal of Combinatorics
Volume 1 (2010)
Spanning trees and orientations of graphs
Pages: 101 – 111
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.
spanning trees, acyclic orientations, cyclic orientations of graphs
2010 Mathematics Subject Classification
05C05, 05C07, 05C20, 05C38