Cycle intersection in spanning trees: A shorter proof of a conjecture and applications

Abstract

Consider a connected simple graph G. Given a spanning tree T of G, for each edge e in G but not in T , a cycle Ce is formed by adding the edge e to the path in T that connects the endpoints of e. The Minimum Spanning Tree Cycle Intersection problem (MSTCI for short) consists in finding a spanning tree for G that minimizes the number of intersections between this type of cycles. This problem was introduced in 2021 and its solution turned out to be difficult for general graphs, without an efficient algorithm to solve it. It was then conjectured that a solution of the problem for a graph that has a universal vertex u is the star centered at u. The conjecture was quickly proven true. In this note, we give a proof of the conjecture that is shorter than the one that has already been published. It is based on a single lemma about domination. We also explore the connections between this lemma and some graph classes, like chordal graphs and dually chordal graphs.