On the average size of $1$-nearly independent vertex sets in graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917046117203968 |
|---|---|
| author | Dossou-Olory, Audace A. V. Andriantiana, Eric O. |
| author_facet | Dossou-Olory, Audace A. V. Andriantiana, Eric O. |
| contents | A $k$-nearly independent vertex subset of a graph $G$ is a set of vertices that induces a subgraph containing exactly $k$ edges. For $k = 0$, this coincides with the classical notion of independent subsets. This paper investigates the average size, $av_1(G)$ of the $1$-nearly independent vertex subsets of both graphs and trees of a given order $n$.
Let $E_n$ denote the $n$-vertex edgeless graph, so that $av_1(E_n) = 0$. We determine all $n$-vertex graphs $G\neq E_n$ that minimize or maximize $av_1$. Similarly, we identify the trees of order $n$ that achieve the minimum value of $av_1$, and prove that the maximum value lies between $n/2$ and $(n+1)/2$ if $n>8$. Finally, we construct a family of $n$-vertex trees which shows that the bounds are asymptotically sharp. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_23670 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the average size of $1$-nearly independent vertex sets in graphs Dossou-Olory, Audace A. V. Andriantiana, Eric O. Combinatorics Primary 05C30, 05C69, secondary 05C35, 05C75 A $k$-nearly independent vertex subset of a graph $G$ is a set of vertices that induces a subgraph containing exactly $k$ edges. For $k = 0$, this coincides with the classical notion of independent subsets. This paper investigates the average size, $av_1(G)$ of the $1$-nearly independent vertex subsets of both graphs and trees of a given order $n$. Let $E_n$ denote the $n$-vertex edgeless graph, so that $av_1(E_n) = 0$. We determine all $n$-vertex graphs $G\neq E_n$ that minimize or maximize $av_1$. Similarly, we identify the trees of order $n$ that achieve the minimum value of $av_1$, and prove that the maximum value lies between $n/2$ and $(n+1)/2$ if $n>8$. Finally, we construct a family of $n$-vertex trees which shows that the bounds are asymptotically sharp. |
| title | On the average size of $1$-nearly independent vertex sets in graphs |
| topic | Combinatorics Primary 05C30, 05C69, secondary 05C35, 05C75 |
| url | https://arxiv.org/abs/2510.23670 |