论文标题
关于最大独立集的数量：从月亮摩泽
On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza
论文作者
论文摘要
我们将有关最大独立集数量的极端图理论中的两个经典结果连接。 $ n $ vertex图中最大独立集的最大数字MIS $（N）$由Moon和Moser确定。 Hujter和Tuza确定了$ n $ vertex的无三角形图中最大独立集的最大数字$ _ \ bigtriangleup（n）$。我们确定最大数字MIS $ _T（n）$最大独立集中的$ n $ vertex图中，其中包含$ t $ t+1 $的诱导三角形匹配。我们还谴责了卡恩（Kahn）和帕克（Park）的稳定性结果，最大数字$ _ {\ bigtriangleup，t}（n）$最大独立集中在$ n $ n $ -vertex三角形图中，没有诱导的匹配尺寸$ t+1 $。
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$_\bigtriangleup(n)$ of maximal independent sets in an $n$-vertex triangle-free graph was determined by Hujter and Tuza. We determine the maximum number mis$_t(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$_{\bigtriangleup,t}(n)$ of maximal independent sets in an $n$-vertex triangle-free graphs containing no induced matching of size $t+1$.
