### Abstract

A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|\geq \lceil 3(|V|-1)/2\rceil$, and constructed a large class of immune graphs attaining this lower bound for every value of $|V(G)|$, called ABC graphs. In this paper, we prove their conjecture that every immune graph that attains this lower bound is an ABC graph.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente |

Number of pages | 40 |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2005 |

### Publication series

Name | Memorandum Afdeling TW |
---|---|

Publisher | Department of Applied Mathematics, University of Twente |

No. | 1769 |

ISSN (Print) | 0169-2690 |

### Keywords

- MSC-05C75
- MSC-05C35
- METIS-225440
- IR-65953
- EWI-3589

## Cite this

Bonsma, P. S. (2005).

*A characterization of extremal graphs without matching-cuts*. (Memorandum Afdeling TW; No. 1769). Enschede: University of Twente.