Spanning trees and orientations of graphs
Spanning trees and orientations of graphs
复制标题
DOI：
10.4310/joc.2010.v1.n2.a1
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
C. Thomassen
中科院分区：
文献类型：
--
作者：
C. Thomassen
美利奴和Welsh的一个猜想是：无环无桥多重图G的生成树数τ（G）总是小于或等于无圈方向数a（G），或全圈方向数c（G），即每条边都在有向圈中的方向。本文证明了τ（G）≤ c（G）ifG至少有4 n条边，若G至多有16 n/15条边，则τ（G）≤ a（G）.我们还证明了对所有最大度不超过3的重图，τ（G）≤ a（G），从而对任何平面三角剖分，τ（G）≤ c（G）.
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 )i fG 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.