Back to Search
Start Over
Maximal independent sets in graphs with given matching number
- Publication Year :
- 2024
-
Abstract
- 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.
- Subjects :
- Mathematics - Combinatorics
05C69, 05C30, 05C70
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2412.15950
- Document Type :
- Working Paper