Graphs with Maximum Edge-Integrity

The edge-integrity of a graph \(G\) is given by the minimum of \(|S|+m(G-S)\) taken over all \(S \subseteq E(G)\), where \(m(G-S)\) denotes the maximum order of a component of \(G-S\). An honest graph is one with maximum edge-integrity (viz. its order). In this paper, lower and upper bounds on the edge-integrity of a graph with given order and diameter are investigated. For example, it is shown that the diameter of an honest graph on \(n\) vertices is at most \(\sqrt{8n}-3\), and this is sharp. Also, a lower bound for the edge-integrity of a graph in terms of its eigenvalues is established. This is used to show that for \(d\) sufficiently large, almost all \(d\)-regular graphs are honest.