Regular honest graphs, isoperimetric numbers, and bisection of weighted graphs (Q1306928)

The edge-integrity of a graph \(G\) is defined by \(I'(G)= \min\{|S|+ m(G- S):S\subset E\}\) where \(m(H)\) denotes the maximum order of a component of \(H\). \textit{K. S. Bagga}, \textit{L. W. Beineke}, \textit{M. J. Lipman} and \textit{R. E. Pippert} [Congr. Numerantium 60, 141-144 (1987; Zbl 0664.05039)] called a graph honest if its edge-integrity is equal to the order of the graph. \textit{M. J. Lipman} [Congr. Numerantium 85, 184-192 (1991; Zbl 0765.05094)] showed that there are exactly twenty honest cubic graphs. Here the authors prove that any honest graph with maximum degree 4 has at most \(10^{60}\) vertices but that for \(k\geq 6\), almost all \(k\)-regular graphs are honest. The question of whether the number of 5-regular honest graphs is finite remains unanswered. It should be noted that \textit{L. W. Beineke}, \textit{W. Goddard} and \textit{M. J. Lipman} [Ars Combin. 46, 119-127 (1997; Zbl 0933.05072)] had previously shown that for sufficiently large \(k\), almost all \(k\)-regular graphs are honest.