## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 469-481 |

Number of pages | 13 |

Journal | European Journal of Combinatorics |

Volume | 20 |

Issue number | 6 |

DOIs | |

State | Published - Aug 1999 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics