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
SN - 0195-6698
VL - 20
SP - 469
EP - 481
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
IS - 6
ER -