The minimum number of maximal independent sets in graphs with given order and independence number
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916449508917248 |
|---|---|
| author | Tian, Yuting Tu, Jianhua |
| author_facet | Tian, Yuting Tu, Jianhua |
| contents | 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)\geq f(n-α),\]
and for any unicyclic graph $G$ with $n$ vertices and independence number $α$,
\begin{align*}
mis(G)\geq
\begin{cases}
2, & \text{if} \ n=4\ \text{and}\ α=2,
3, & \text{if} \; α=n-2 \; \text{and} \; n\neq4,
2f(n-α), & \text{if} \; n\geq 5\; \text{and}\; \lceil \frac{n}{2} \rceil \leq α< n-2,
f(n-α+2)-f(n-α-3), &\text{if} \; n\geq 5, \;\text{and}\ n \; \text{is odd}, \; \text{and} \; α= \lfloor \frac{n}{2} \rfloor,
\end{cases}
\end{align*}
where $f(n)$ represent the $n$th Fibonacci number. Moreover, we also show that the above inequalities are sharp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17717 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The minimum number of maximal independent sets in graphs with given order and independence number Tian, Yuting Tu, Jianhua Combinatorics 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)\geq f(n-α),\] and for any unicyclic graph $G$ with $n$ vertices and independence number $α$, \begin{align*} mis(G)\geq \begin{cases} 2, & \text{if} \ n=4\ \text{and}\ α=2, 3, & \text{if} \; α=n-2 \; \text{and} \; n\neq4, 2f(n-α), & \text{if} \; n\geq 5\; \text{and}\; \lceil \frac{n}{2} \rceil \leq α< n-2, f(n-α+2)-f(n-α-3), &\text{if} \; n\geq 5, \;\text{and}\ n \; \text{is odd}, \; \text{and} \; α= \lfloor \frac{n}{2} \rfloor, \end{cases} \end{align*} where $f(n)$ represent the $n$th Fibonacci number. Moreover, we also show that the above inequalities are sharp. |
| title | The minimum number of maximal independent sets in graphs with given order and independence number |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.17717 |