Minimum Spanning Tree Cycle Intersection Problem
Minimum Spanning Tree Cycle Intersection Problem
复制标题
DOI：
10.1016/j.dam.2021.01.031
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
M. Dubinsky;C. Massri;G. Taubin
中科院分区：
文献类型：
--
作者：
M. Dubinsky;C. Massri;G. Taubin
考虑一个连通图 G，并令 T 为 G 的生成树。每条边 e∈ G− T 都会在 T∪{e} 中引发一个循环。两个不同的此类循环的交集是属于两个循环的 T 边的集合。我们考虑寻找具有最少此类非空交集的生成树的问题。在本文中，我们分析了完全图的特殊情况，并对具有通用顶点的图提出了猜想。
Consider a connected graph G and let T be a spanning tree of G. Every edge e∈ G− T induces a cycle in T∪{e}. The intersection of two distinct such cycles is the set of edges of T that belong to both cycles. We consider the problem of finding a spanning tree that has the least number of such non-empty intersections. In this article we analyze the particular case of complete graphs, and formulate a conjecture for graphs that have a universal vertex.