Integrity in Graphs: Bounds and Basics

The integrity of a graph \(G\), denoted \(I(G)\), is defined by \(I(G) = \min\{|S| + m(G – S) : S \subset V(G)\}\) where \(m(G – S)\) denotes the maximum order of a component of \(G – S\); further an \(I\)-set of \(G\) is any set \(S\) for which the minimum is attained. Firstly some useful concepts are formalised and basic properties of integrity and \(I\)-sets identified. Then various bounds and interrelationships involving integrity and other well-known graphical parameters are considered, and another formulation introduced from which further bounds are derived. The paper concludes with several results on the integrity of circulants.