Integrity of Regular Graphs and Integrity Graphs

The integrity of a graph \(G\), \(I(G)\), is defined by \(I(G) = min_{S \subseteq V(G)}\{|S| + m(G – S)\}\) where \(m(G – S)\) is the maximum order of the components of \(G – S\). In general, the integrity of an \(r\)-regular graph is not known [8]. We answer the following question for special regular graphs. For any given two integers \(p\) and \(r\) such that \(\frac{pr}{2}\) is an integer, is there an \(r\)-regular graph, say \(G^*\), on \(p\) vertices having size \(q = \frac{pr}{2}\) such that
\[I(G(p,\frac{pr}{2})) \leq I(G^*)\]
for all \(p\) and \(r\)? The \emph{integrity graph} is denoted by \(IG(p,n)\). It is a graph with \(p\) vertices, integrity \(n\), and has the least number of edges denoted by \(q[p,n]\). We compute \(q[p,n]\) for some values of \(p,n\).