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

Palmer, Cory and Patkós, Balázs (2023) On the number of maximal independent sets : From Moon–Moser to Hujter–Tuza. JOURNAL OF GRAPH THEORY, 104 (2). pp. 440-445. ISSN 0364-9024

Preview

Text 2205.04082v1.pdf Available under License Creative Commons Attribution. Download (114kB) | Preview

Abstract

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

Actions (login required)

Edit Item