Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.09067 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910524367699968 |
|---|---|
| author | Shozi, Zekhaya B. |
| author_facet | Shozi, Zekhaya B. |
| contents | Let $G=(V(G),E(G))$ be a graph with set of vertices $V(G)$ and set of edges $E(G)$. For $k\ge 0$ an integer, a subset $I_k$ of $V(G)$ is called a $k$-nearly independent vertex subset of $G$ if $I_k$ induces a subgraph of size $k$ in $G$. The number of such subsets in $G$ is denoted by $σ_k(G)$. In this paper we continue the study of $σ_1$. In particular, we prove the lower bound on $σ_1$ for a connected graph that contains a cycle and also characterise the two extremal graphs. This improves the result obtained in [E. O. D. Andriantiana and Z. B. Shozi. The number of 1-nearly independent vertex subsets. \textit{Quaestiones Mathematicae}, accepted]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09067 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An improved lower bound on the number of $1$-nearly independent vertex subsets Shozi, Zekhaya B. Combinatorics Let $G=(V(G),E(G))$ be a graph with set of vertices $V(G)$ and set of edges $E(G)$. For $k\ge 0$ an integer, a subset $I_k$ of $V(G)$ is called a $k$-nearly independent vertex subset of $G$ if $I_k$ induces a subgraph of size $k$ in $G$. The number of such subsets in $G$ is denoted by $σ_k(G)$. In this paper we continue the study of $σ_1$. In particular, we prove the lower bound on $σ_1$ for a connected graph that contains a cycle and also characterise the two extremal graphs. This improves the result obtained in [E. O. D. Andriantiana and Z. B. Shozi. The number of 1-nearly independent vertex subsets. \textit{Quaestiones Mathematicae}, accepted]. |
| title | An improved lower bound on the number of $1$-nearly independent vertex subsets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.09067 |