























In this paper, we address the Ehrenborg's conjecture which proposes that for any bipartite graph the number of spanning trees does not exceed the product of the degrees of the vertices divided by the product of the sizes of the graph components. We show that the conjecture is true for a one-side regular graph (that is a graph for which all degrees of the vertices of at least one of the components are equal). We also present a new proof of the fact that the equality holds for Ferrers graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。