Ratio of the number of $\mathbf{1}$-nearly independent vertex subsets and the Merrifield-Simmons index

Audace A. V. Dossou-Olory; Eric O. D. Andriantiana; Valisoa R. M. Rakotonarivo; Zekhaya B. Shozi

Ratio of the number of $\mathbf{1}$-nearly independent vertex subsets and the Merrifield-Simmons index

Audace A. V. Dossou-Olory, Eric O. D. Andriantiana, Valisoa R. M. Rakotonarivo, Zekhaya B. Shozi

arXivarxiv/2604.11813Apr 10, 2026math.COscore 0

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.

Source JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.11813
curl -X POST /api/v1/records/arxiv/2604.11813/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.11813/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'