Ratio of the number of $\mathbf{1}$-nearly independent vertex subsets and the Merrifield-Simmons index
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914469893898240 |
|---|---|
| author | Dossou-Olory, Audace A. V. Andriantiana, Eric O. D. Rakotonarivo, Valisoa R. M. Shozi, Zekhaya B. |
| author_facet | Dossou-Olory, Audace A. V. Andriantiana, Eric O. D. Rakotonarivo, Valisoa R. M. Shozi, Zekhaya B. |
| contents | The number $σ_k(G)$ of induced subgraphs with size $k$ of a graph $G$ was introduced recently as the number of $k$-nearly independent vertex subsets of $G$. Results highlighting similarity and difference in the behaviours of $σ_1$ and $σ_0$, have been reported. In this paper, we provide more comparison tools, by studying the ratio $\frac{σ_1(G)}{σ_{0}(G)}$. We establish sharp lower and upper bounds for this ratio over various classes of graphs, including connected graphs, trees, and forests. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11813 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Ratio of the number of $\mathbf{1}$-nearly independent vertex subsets and the Merrifield-Simmons index Dossou-Olory, Audace A. V. Andriantiana, Eric O. D. Rakotonarivo, Valisoa R. M. Shozi, Zekhaya B. Combinatorics Primary 05C30, 05C69, Secondary 05C35, 05C75 The number $σ_k(G)$ of induced subgraphs with size $k$ of a graph $G$ was introduced recently as the number of $k$-nearly independent vertex subsets of $G$. Results highlighting similarity and difference in the behaviours of $σ_1$ and $σ_0$, have been reported. In this paper, we provide more comparison tools, by studying the ratio $\frac{σ_1(G)}{σ_{0}(G)}$. We establish sharp lower and upper bounds for this ratio over various classes of graphs, including connected graphs, trees, and forests. |
| title | Ratio of the number of $\mathbf{1}$-nearly independent vertex subsets and the Merrifield-Simmons index |
| topic | Combinatorics Primary 05C30, 05C69, Secondary 05C35, 05C75 |
| url | https://arxiv.org/abs/2604.11813 |