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

Abstract

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^{\prime })|E(T)\mathrm{\Delta }E(T^{\prime })=\{e,f\},e\in E(T),f\in E(T^{\prime })\text{ and }e\text{ and }f\text{ are incident with a vertex }v\text{ of degree }1\text{ in }T\text{ and }{T}^{\prime }\}$. $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$.