Journal of Combinatorics
Volume 1 (2010)
Number 2
Spanning trees and orientations of graphs
Pages: 101 – 111
DOI: https://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 of a loopless and bridgeless multigraph is always less than or equal to either the number of acyclic orientations, or the number of totally cyclic orientations, that is, orientations in which every edge is in a directed cycle. We prove that if has at least edges, and that if has at most edges. We also prove that for all multigraphs of maximum degree at most and consequently for any planar triangulation.
Keywords
spanning trees, acyclic orientations, cyclic orientations of graphs
2010 Mathematics Subject Classification
05C05, 05C07, 05C20, 05C38
Published 1 January 2010