Maximal independent sets in graphs with given matching number

Yongtang Shi, Jianhua Tu, Ziyuan Wang

Published 2024-12-20Version 1

In a graph $G$, a maximal independent set $I$ is a set of vertices such that no two vertices are adjacent, and the addition of any vertex $v$ not in $I$ would result in a set that is no longer independent. An induced triangle matching in a graph is a set of vertex disjoint triangles forming an induced subgraph, with its size being the number of these triangles. Palmer and Patk\'{o}s [J. Graph Theory 104 (2023) 440--445] have made a significant contribution by establishing an upper bound on the number of maximal independent sets for graphs of given order that do not contain an induced triangle matching of size $t+1$. Building on their work, this paper extends the analysis to determine the maximum number of maximal independent sets in general graphs, connected graphs, triangle-free graphs, and connected triangle-free graphs with given matching number. Additionally, we characterize the corresponding extremal graphs that achieve this maximum.