Journal of Combinatorics

Volume 1 (2010)

Number 2

Spanning trees and orientations of graphs

Pages: 101 – 111

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n2.a1

Author

Carsten Thomassen (Department of Mathematics, Technical University of Denmark, Lyngby, Denmark)

Abstract

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)