TY - JOUR

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

AU - Alon, Noga

AU - Hamburger, Peter

AU - Kostochka, Alexandr V.

N1 - Funding Information:
†Research supported in part by a USA Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences. ‡This work was partially supported by an Indiana University-Purdue University Fort Wayne Scholar-in-Residence Grant, and by the grant 97-01-01075 of the Russian Foundation for Fundamental Research.

PY - 1999/8

Y1 - 1999/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0347090750&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347090750&partnerID=8YFLogxK

U2 - 10.1006/eujc.1998.0295

DO - 10.1006/eujc.1998.0295

M3 - Article

AN - SCOPUS:0347090750

VL - 20

SP - 469

EP - 481

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

IS - 6

ER -