2024/10/23 by Yuting Tian, Tian, Yuting, Jianhua Tu +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2410.17717
openalex publication_date 2024/10/23 · openalex created_date 2024/11/13 · openalex updated_date 2026/07/28
Let MIS(G) be the set of all maximal independent sets in a graph G, and let mis(G)=|MIS(G)|. In this paper, we show that for any tree T with n vertices and independence number α, mis(T)≥ f(n-α), and for any unicyclic graph G with n vertices and independence number α, mis(G)≥ \begincases 2, amp; if n=4 and α=2, 3, amp; if α=n-2 and n≠4, 2f(n-α), amp; if n≥ 5 and \lceil (n)/(2) \rceil ≤ αlt; n-2, f(n-α+2)-f(n-α-3), amp;if n≥ 5, and n is odd, and α= \lfloor (n)/(2) \rfloor, \endcases where f(n) represent the nth Fibonacci number. Moreover, we also show that the above inequalities are sharp.