On the Toughness of Some Generalized Petersen Graphs

Abstract

Upper and lower bounds are established for the toughness of the generalized Petersen graphs $G(n,2)$ for $n\ge 5$, and all non-isomorphic disconnecting sets that achieve the toughness are presented for $5\le n\le 15$. These results also provide an infinite class of $G(n,2)$ for which the toughness equals $\frac{5}{4}$, namely when $n\equiv 0(\mathrm{mod}7)$.