Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs

The edge-integrity of a graph G is I′ (G) := min{|S| + m(G - S) : S ⊂ E}, where m(H) denotes the maximum order of a component of H. A graph G is called honest if its edge-integrity is the maximum possible; that is, equals the order of the graph. The only honest 2-regular graphs are the 3-, 4-, and 5-cycles. Lipman [13] proved that there are exactly twenty honest cubic graphs. In this paper we exploit a technique of Bollobás [8,9] to prove that for every k ≥ 6, almost all k-regular graphs are honest. On the other hand, we show that there are only finitely many 4-regular honest graphs. To prove this, we use a weighted version of the upper bound on the isoperimetric number due to Alon [1]. We believe that this version is of interest by itself.