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

Noga Alon, Peter Hamburger, Alexandr V. Kostochka

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)469-481
Number of pages13
JournalEuropean Journal of Combinatorics
Issue number6
StatePublished - Aug 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs'. Together they form a unique fingerprint.

Cite this