Extremal graphs with no subgraph admitting $k+1$ edge-disjoint spanning trees

Abstract

A graph $G$ is $\ddot{I}{„}_k$-maximal if $G$ contains no subgraph admitting $k+1$ edge-disjoint spanning trees, while the addition of any edge in the complement of $G$ yields a subgraph that admits $k+1$ edge-disjoint spanning trees. In this paper, we prove that for any integers $k\ge 1$ and $n\ge 2k+2$, every $\ddot{I}{„}_k$-maximal graph of order $n$ satisfies $|E(G)|\le (k+1)(n-1)-1$. Furthermore, we construct a family of $\ddot{I}{„}_k$-maximal graphs on $n\ge 2k+2$ vertices that have exactly $(k+1)(n-1)-1$ edges, which establishes the tightness of the upper bound. Then we conjecture that every $\ddot{I}{„}_k$-maximal graph on $n$ vertices has exactly $(k+1)(n-1)-1$ edges, and we verify the conjecture for the case $k=1$.