A note on spanning trees and totally cyclic orientations of 3-connected graphs

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

Full Text (PDF format)

Published 16 May 2013