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\{\frac{|E(G)|}{w(G-X)}\mid Xisanedge-cutsetofG\},$$

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)\le \lambda (G).$ In this paper we prove that for any integer $r$, $r>2$ and any rational number $s$ with $\frac{r}{2}<s\le r$, there always exists a balanced graph $G$ such that $\lambda (G)=r$ and ${\tau }_1(G)=s$.