On the Existence of Balanced Graphs with Given Edge-Toughness and Edge-Connectivity

Abstract

The edge-toughness \(\tau_1(G)\) of a graph \(G\) is defined as

\[\tau_1(G) = \min\left\{\frac{|E(G)|}{w(G-X)} \mid X { is an edge-cutset of } G\right\},\]

where \(w(G-X)\) denotes the number of components of \(G-X\). Call a graph \(G\) balanced if \(\tau_1(G) = \frac{|E(G)|}{w(G-E(G))-1}\). It is known that for any graph \(G\) with edge-connectivity \(\lambda(G)\),
\(\frac{\lambda(G)}{2} < \tau_1(G) \leq \lambda(G).\) In this paper we prove that for any integer \(r\), \(r > 2\) and any rational number \(s\) with \(\frac{r}{2} < s \leq r\), there always exists a balanced graph \(G\) such that \(\lambda(G) = r\) and \(\tau_1(G) = s\).