Minimum Spanning Tree Cycle Intersection problem

Abstract

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.