Equi-Toughness Partitions of Graphs

Abstract

Let $G=(V,E)$ be a simple graph. Let $S$ be a subset of $V(G)$. The toughness value of $S$, denoted by $T_S$, is defined as $\frac{|S|}{\omega (G–S)}$, where $\omega (G–S)$ denotes the number of components in $G–S$. If $S=V$, then $\omega (G–S)$ is taken to be $1$ and hence $T_{V(G)}=|V(G)|$. A partition of $V(G)$ into subsets $V_1,V_2,\dots ,V_t$ such that $T_{V_i}$, $1\le i\le t$, is a constant is called an equi-toughness partitio of $G$. The maximum cardinality of such a partition is called the equi-toughness partition number of $G$ and is denoted by $ET(G)$. The existence of $ET$-partition is guaranteed. In this paper, a study of this new parameter is initiated.