The Connectivity Of The Leaf-Exchange Spanning Tree Graph Of A Graph

Let \(G\) be a connected (multi)graph. We define the leaf-exchange spanning tree graph \( {T_l}\) of \(G\) as the graph with vertex set \(V_l = \{T|T \text{ is a spanning tree of } G\}\) and edge set \(E_l = \{(T, T’)|E(T)\Delta E(T’) = \{e, f\}, e \in E(T), f \in E(T’) \text{ and } e \text{ and } f \text{ are incident with a vertex } v \text{ of degree } 1 \text{ in } T \text{ and } T’\}\). \({T}(G)\) is a spanning subgraph of the so-called spanning tree graph of \(G\), and of the adjacency spanning tree graph of \(G\), which were studied by several authors. A variation on the leaf-exchange spanning tree graph appeared in recent work on basis graphs of branching greedoids. We characterize the graphs which have a connected leaf-exchange spanning tree graph and give a lower bound on the connectivity of \( {T_l}(G)\) for a \(3\)-connected graph \(G\).