## Abstract

We connect two classical results in extremal graph theory concerning the number of maximal independent sets. The maximum number (Figure presented.) of maximal independent sets in an (Figure presented.) -vertex graph was determined by Miller and Muller and independently by Moon and Moser. The maximum number (Figure presented.) of maximal independent sets in an (Figure presented.) -vertex triangle-free graph was determined by Hujter and Tuza. We give a common generalization of these results by determining the maximum number (Figure presented.) of maximal independent sets in an (Figure presented.) -vertex graph containing no induced triangle matching of size (Figure presented.). This also improves a stability result of Kahn and Park on (Figure presented.). Our second result is a new (short) proof of a second stability result of Kahn and Park on the maximum number (Figure presented.) of maximal independent sets in (Figure presented.) -vertex triangle-free graphs containing no induced matching of size (Figure presented.).

Original language | English |
---|---|

Pages (from-to) | 440-445 |

Number of pages | 6 |

Journal | Journal of Graph Theory |

Volume | 104 |

Issue number | 2 |

DOIs | |

State | Published - Oct 2023 |

## Keywords

- extremal graph theory
- induced (triangle) matchings
- maximal independent sets
- stability results