Equi-Integraty Partitions in Graphs


R. Sundareswaran, V. Swaminathan




C.\,A. Barefoot, et. al. introduced the concept of the integrity of a graph. It is an useful measure of vulnerability and it is defined as follows $I(G)=\min\{|S|+m(G-S):S\subset V(G)\}$, where $m(G-S)$ denotes the order of the largest component in $G-S$. The integrity of the set $S$ is defined as $|S|+m(G-S)$ and is denoted by $I_S$, where $m(G-S)$ denotes the order of maximum component in $G-S$. A partition of $V(G)$ into subsets $V_1,V_2,\ldots,V_t$ such that $I_{V_i},1\leq i\leq t$ is a constant is called equi-integrity partition of $G$. The maximum cardinality of such a partition is called equi-integrity partition number of $G$ and is denoted by $EI(G)$. Since $V(G)$ itself is an equi-integrity partition of $G$, the existence of $EI$-partition is guaranteed. In this paper, a study of this new parameter is initiated.