Back to Search Start Over

Maximal independent sets in graphs with given matching number

Authors :
Shi, Yongtang
Tu, Jianhua
Wang, Ziyuan
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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2412.15950
Document Type :
Working Paper