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 τ(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 τ(G)c(G) if G has at least 4n edges, and that τ(G)a(G) if G has at most 16n/15 edges. We also prove that τ(G)a(G) for all multigraphs of maximum degree at most 3 and consequently τ(G)c(G) 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