On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza

preprint2022arXivOpen access

Abstract

We connect two classical results in extremal graph theory concerning the number of maximal independent sets. The maximum number mis(n)(n) of maximal independent sets in an nn-vertex graph was determined by Moon and Moser. The maximum number mis△(n)_\bigtriangleup(n) of maximal independent sets in an nn-vertex triangle-free graph was determined by Hujter and Tuza. We determine the maximum number mist(n)_t(n) of maximal independent sets in an nn-vertex graph containing no induced triangle matching of size t+1t+1. We also reprove a stability result of Kahn and Park on the maximum number mis△,t(n)_{\bigtriangleup,t}(n) of maximal independent sets in an nn-vertex triangle-free graphs containing no induced matching of size t+1t+1.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.