Journal of Combinatorics

Volume 4 (2013)

Number 1

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

Pages: 95 – 104

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n1.a5

Author

Fenggen Lin (College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian, China)

Abstract

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)