Equitable Partitions to Spanning Trees in a Graph
Equitable Partitions to Spanning Trees in a Graph
复制标题
图中生成树的公平划分
DOI：
--
复制
发表时间：
2011
影响因子：
0.7
通讯作者：
J. Szabó
中科院分区：
文献类型：
--
作者：
Zsolt Fekete;J. Szabó
在本文中，我们首先证明，如果一个无向图的边集是它的两个生成树的不相交的联合，那么对于每一个子集$P$的边缘存在一个生成树分解，削减$P$成两个（几乎）相等的部分。该论文的主要结果是这一主张的进一步扩展：如果一个图的边集是它的两个生成树的不交并，那么对于每个稳定的顶点集的大小为3，存在这样一个生成树分解，将这些顶点的星切割成（几乎）相等的部分。此结果不符合4而不是3。证明是基本的。
In this paper we first prove that if the edge set of an undirected graph is the disjoint union of two of its spanning trees, then for every subset $P$ of edges there exists a spanning tree decomposition that cuts $P$ into two (almost) equal parts. The main result of the paper is a further extension of this claim: If the edge set of a graph is the disjoint union of two of its spanning trees, then for every stable set of vertices of size 3, there exists such a spanning tree decomposition that cuts the stars of these vertices into (almost) equal parts. This result fails for 4 instead of 3. The proofs are elementary.