Minimum Tenacity of Toroidal graphs

Abstract

The tenacity of a graph <em>G</em>,<em> T</em>(<em>G</em>), is de ned by <em>T</em>(<em>G</em>) = min{[|<em>S</em>|+<em>τ</em>(<em>G</em>-<em>S</em>)]/[<em>ω</em>(<em>G</em>-<em>S</em>)]}, where the minimum is taken over all vertex cutsets<em> S</em> of <em>G</em>. We de ne <em>τ</em>(<em>G</em> - <em>S</em>) to be the number of the vertices in the largest component of the graph <em>G</em> -<em> S</em>, and <em>ω</em>(<em>G</em> - <em>S</em>) be the number of components of <em>G</em> - <em>S</em>.In this paper a lower bound for the tenacity <em>T</em>(<em>G</em>) of a graph with genus <em>γ</em>(<em>G</em>) is obtained using the graph's connectivity <em>κ</em> (<em>G</em>). Then we show that such a bound for almost all toroidal graphs is best possible.