Journal of Combinatorics
Volume 4 (2013)
A note on spanning trees and totally cyclic orientations of 3-connected graphs
Pages: 95 – 104
Merino and Welsh conjectured that for a 2-edge connected graph $G$ with no loops, the number of spanning trees of $G$ is always less than or equal to either the number of acyclic orientations of $G$, or the number of totally cyclic orientations of $G$. In this paper, we prove that the Merino-Welsh conjecture holds for a 3-connected simple graph of minimum degree at least 4 and average degree at least 7.02.
2010 Mathematics Subject Classification
05C05, 05C20, 05C31
Published 16 May 2013