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.